Submission #691569

#TimeUsernameProblemLanguageResultExecution timeMemory
691569ismayilArranging Shoes (IOI19_shoes)C++17
100 / 100
315 ms32972 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; const int MAX = 2e5 + 5; ll bit[MAX]; int n; void update(int pos, int val){ for(int i = pos; i < n; i = i | (i + 1)) bit[i] += val; } ll query(int pos){ ll res = 0; for(int i = pos; i >= 0; i = (i & (i + 1)) - 1) res += bit[i]; return res; } ll query(int l, int r){ if(l == 0) return query(r); return query(r) - query(l - 1); } ll count_swaps(vector<int> S){ map<int, set<int>> m; n = S.size(); for (int i = 0; i < n; i++) { m[S[i]].insert(i); update(i, 1); } ll ans = 0; for (int i = 0; i < n; i++) { if(query(i, i) == 0) continue; set<int> &s = m[-S[i]]; auto it = s.upper_bound(i); int idx = (*it); if(S[i] >= 0) ans += query(i, idx - 1); else ans += query(i + 1, idx - 1); update(idx, -1); s.erase(it); } 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...