Submission #486823

#TimeUsernameProblemLanguageResultExecution timeMemory
486823HaidaraArranging Shoes (IOI19_shoes)C++17
0 / 100
6 ms9676 KiB
#include<bits/stdc++.h> #include<shoes.h> #define rep(i,x,n) for(int i=(x);i<(n);i++) #define FOR(i,n) rep(i,0,n) #define v(i) vector< i > #define ll long long using namespace std; const ll inf=1LL<<62LL; const ll mod=1e9+7; const ll maxn=100200; ll st[maxn]; int n; int query(int ql,int qr,int l=1,int r=n,int inx=1) { if(ql<=l&&r<=qr) return st[inx]; if(ql>r||l>qr) return 0; int mid=l+(r-l)/2; return query(ql,qr,mid+1,r,inx*2+1)+query(ql,qr,l,mid,inx*2); } void update(int pos,int val=0,int l=1,int r=n,int inx=1) { if(l==r) { st[inx]=val; return ; } int mid=l+(r-l)/2; if(mid<=pos) update(pos,val,l,mid,inx*2); else update(pos,val,mid+1,r,inx*2+1); st[inx]=st[inx*2]+st[inx*2+1]; } ll count_swaps(v(int)a) { ll ans=0; n=a.size(); FOR(i,n) update(i+1,1); set<int>posl[maxn],posr[maxn]; FOR(i,n) if(a[i]<0) posl[-a[i]].insert(i); else posr[a[i]].insert(i); v(bool)vis(maxn,0); FOR(i,n) { if(vis[i]) continue; if(a[i]>0) ans++; a[i]=abs(a[i]); int right=*posr[a[i]].begin(); int left=*posl[a[i]].begin(); posl[a[i]].erase(posl[a[i]].begin()); posr[a[i]].erase(posr[a[i]].begin()); vis[right]=1; vis[left]=1; if(left>right) swap(left,right); ans+=(query(left+2,right)-1); update(left+1); update(right+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...