IndeedなうB:E問題:
たまによく見る。
問題:E: Line up! - Indeedなう(オープンコンテストB) | AtCoder
解法:目的の形にするためにはとにかく小さい数から順に左に詰めていかなければならない。それをBITとか使ってシミュレーションすれば良いだけ。
以下ソースコード
const int MAXN = 100100; int H[MAXN]; set<int> s; int bit[MAXN]; int n; int sum(int i) { int ss = 0; while (i > 0) { ss += bit[i]; i -= i&-i; } return ss; } void add(int i, int x) { while (i <= n) { bit[i] += x; i += i&-i; } } vector<pair<int, int> > pos; int main(void) { cin >> n; bool ng = false; for (int i = 1; i <= n; i++) { cin >> H[i]; if (s.find(H[i]) != s.end()) ng = true; s.insert(H[i]); add(i, 1); pos.push_back(make_pair(H[i], i)); } sort(pos.begin(), pos.end()); if (ng) { cout << -1 << endl; return 0; } ll ans = 0; for (int i = 0; i < n; i++) { ans += (ll)pos[i].first * sum(pos[i].second-1); add(pos[i].second, -1); } cout << ans << endl; return 0; }