Submission #1172551

#TimeUsernameProblemLanguageResultExecution timeMemory
1172551versesrevArranging Shoes (IOI19_shoes)C++20
100 / 100
230 ms146264 KiB
// 22:48 #include <vector> #include <unordered_map> #include <queue> long long count_swaps(std::vector<int> ss) { int n2 = ss.size(); std::unordered_map<int, std::queue<int>> poss; for (int i = 0; i < n2; ++i) { poss[ss[i]].push(i); } std::vector<int> tree(n2 + 1, 0); auto update = [&](int pos, int val) { ++pos; for (; pos <= n2; pos += (pos & -pos)) { tree[pos] += val; } }; auto query = [&](int pos) { ++pos; int r = 0; for (; pos > 0; pos -= (pos & -pos)) { r += tree[pos]; } return r; }; auto range_query = [&](int le, int ri) { if (ri < le) return 0; return query(ri) - query(le - 1); }; for (int i = 0; i < n2; ++i) update(i, 1); long long ans = 0; for (int i = 0; i < n2; ++i) { if (range_query(i, i) == 0) { continue; } int val = ss[i]; int val2 = -val; int pos = poss[val].front(); poss[val].pop(); int pos2 = poss[val2].front(); poss[val2].pop(); ans += range_query(pos + 1, pos2 - 1); if (val > 0) ans += 1; update(pos, -1); update(pos2, -1); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...