Submission #204166

#TimeUsernameProblemLanguageResultExecution timeMemory
204166medkArranging Shoes (IOI19_shoes)C++14
100 / 100
115 ms15980 KiB
#include <bits/stdc++.h> #include "shoes.h" #define ll long long #define pb push_back #define x first #define y second using namespace std; int n; vector<int> a,bit; vector<vector<int>> p1,p2; void update(int x, int val) { for(;x<=n;x+=x&-x) bit[x]+=val; } ll pre(int x) { ll ret=0; for(;x>0;x-=x&-x) ret+=bit[x]; return ret; } ll sm(int l, int r) { return pre(r)-pre(l-1); } ll count_swaps(vector<int> S) { ll ans=0; n=S.size(); bit.resize(n+1); a.pb(0); for(int i=1;i<=n;i++) a.pb(1), update(i,1); p1.resize(n/2+1), p2=p1; for(int i=0;i<n;i++) { if(S[i]>0) p1[S[i]].pb(i+1); else p2[-S[i]].pb(i+1); } vector<int> pt(n/2+1,0); for(int i=1;i<=n;i++) { if(a[i]==0) continue; if(S[i-1]>0) { ans+=sm(i+1,p2[S[i-1]][pt[S[i-1]]]-1)+1; a[p2[S[i-1]][pt[S[i-1]]]]=0; update(i,-1), update(p2[S[i-1]][pt[S[i-1]]],-1); pt[S[i-1]]++; } else { ans+=sm(i+1,p1[-S[i-1]][pt[-S[i-1]]]-1); a[p1[-S[i-1]][pt[-S[i-1]]]]=0; update(i,-1), update(p1[-S[i-1]][pt[-S[i-1]]],-1); pt[-S[i-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...