Submission #293530

#TimeUsernameProblemLanguageResultExecution timeMemory
293530DystoriaXArranging Shoes (IOI19_shoes)C++14
100 / 100
209 ms139512 KiB
#include "shoes.h" #include <vector> #include <algorithm> #include <deque> #include <bitset> #include <iostream> using namespace std; int n; int bit[200010]; void update(int x, int val){ for(; x <= n; x += x & (-x)) bit[x] += val; } int query(int x){ int ret = 0; for(; x; x -= x & (-x)) ret += bit[x]; return ret; } int query(int l, int r){ if(l > r) return 0; return query(r) - query(l - 1); } bitset<200010> vis; deque<int> lf[100010], rg[100010]; long long count_swaps(vector<int> s) { n = s.size(); int pos = 0; for(auto &k : s){ if(k > 0) rg[k].emplace_back(++pos); else lf[-k].emplace_back(++pos); update(pos, 1); } long long ans = 0; for(int i = 1; i <= n; i++){ // cerr << i << "\n"; if(vis[i]) continue; vis[i] = true; if(s[i - 1] < 0){ int idx = -s[i - 1]; lf[idx].pop_front(); int nxt = rg[idx].front(); rg[idx].pop_front(); ans += query(i + 1, nxt - 1); update(nxt, -1); vis[nxt] = true; } else { int idx = s[i - 1]; rg[idx].pop_front(); int nxt = lf[idx].front(); lf[idx].pop_front(); ans += query(i, nxt - 1); update(nxt, -1); vis[nxt] = true; } // cerr << i << " " << ans << "\n"; update(i, 0); } 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...