제출 #486891

#제출 시각아이디문제언어결과실행 시간메모리
486891HaidaraArranging Shoes (IOI19_shoes)C++17
10 / 100
150 ms109384 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 #define pp push_back using namespace std; const ll inf=1LL<<62LL; const ll mod=1e9+7; const ll maxn=1000200; ll st[4*maxn]; int n; ll query(int ql,int qr,int l=0,int r=n-1,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 l=0,int r=n-1,int inx=1) { if(l==r) { st[inx]=0; return ; } int mid=l+(r-l)/2; if(mid<=pos) update(pos,l,mid,inx*2); else update(pos,mid+1,r,inx*2+1); st[inx]=st[inx*2]+st[inx*2+1]; } int build(int l=0,int r=n-1,int inx=1) { if(l==r) return st[inx]=1; int mid=l+(r-l)/2; return st[inx]=build(l,mid,inx*2)+build(mid+1,r,inx*2+1); } set <int> s[maxn*2]; ll count_swaps(v(int)a) { n=a.size(); build(); FOR(i,n) s[a[i]+n].insert(i+1); ll ans=0; v(bool)vis(maxn,0); FOR(i,n){ if(vis[i+1]) continue; ll poz=*s[-a[i]+n].begin(); s[a[i]+n].erase(i+1); s[-a[i]+n].erase(poz); ans+=query(i-1,poz-1)-2; if(a[i]>0) ans++; update(i); update(poz-1); vis[i+1]=vis[poz]=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...