Submission #768006

#TimeUsernameProblemLanguageResultExecution timeMemory
768006AlmaArranging Shoes (IOI19_shoes)C++14
10 / 100
1 ms212 KiB
#include <bits/stdc++.h> #include "shoes.h" using namespace std; vector<long long> segTree; vector<pair<int, int>> pairs; unordered_map<int, int> pos; void update(int n, int l, int r, int x, int v) { if (l == r) { segTree[n] += v; return; } int m = (l+r) / 2; if (x <= m) update(2*n, l, m, x, v); else update(2*n+1, m+1, r, x, v); segTree[n] = segTree[2*n] + segTree[2*n+1]; } long long query(int n, int l, int r, int lb, int rb) { if (rb < l or r < lb) { return 0; } if (lb <= l and r <= rb) { return segTree[n]; } int m = (l+r) / 2; long long s1 = query(2*n, l, m, lb, rb); long long s2 = query(2*n+1, m+1, r, lb, rb); return s1 + s2; } long long count_swaps(vector<int> s) { int n = s.size(); long long ans = 0; for (int i = 0; i < n; i++) { int x = s[i]; if (pos.find(-x) != pos.end()) { ans += i - pos[-x] - 1; if (x < 0) ans++; pairs.push_back({pos[-x], i}); pos.erase(-x); } else { pos[x] = i; } } sort(pairs.begin(), pairs.end()); segTree = vector<long long>(4*n, 0); for (pair<int, int> p: pairs) { if (p.first+1 != p.second) { ans -= query(1, 0, n-1, p.first+1, p.second-1); } update(1, 0, n-1, p.first, -1); update(1, 0, n-1, p.second, 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...