Submission #230973

#TimeUsernameProblemLanguageResultExecution timeMemory
230973vioalbertArranging Shoes (IOI19_shoes)C++14
100 / 100
341 ms146236 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 2e5+5; int n; ll ft[N]; unordered_map<int, queue<int>> q; void update(int x, ll val) { for(; x <= n+5; x+=x&(-x)) ft[x]+=val; } ll query(int x) { ll ret = 0; for(; x > 0; x-=x&(-x)) ret+=ft[x]; return ret; } ll count_swaps(vector<int> a) { n = a.size(); memset(ft, 0, sizeof ft); ll ans = 0; for(int i = 0; i < n; i++) { bool right = a[i] > 0; if(i > 0 && !q[-a[i]].empty()) { int x = q[-a[i]].front(); q[-a[i]].pop(); ans += query(i+1)-query(x+1); if(!right) ans++; update(x+1, 1); update(i+2, -1); } else { q[a[i]].push(i); } update(i+1, 1); } q.clear(); 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...