Submission #1230130

#TimeUsernameProblemLanguageResultExecution timeMemory
1230130warrennArranging Shoes (IOI19_shoes)C++20
100 / 100
382 ms285656 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long vector<ll>st,lazy; ll n; void prop(ll idx,ll l,ll r){ //if(l==4 && r==7)cout<<"y"<<endl; if(l!=r){ lazy[2*idx+1]+=lazy[idx]; lazy[2*idx+2]+=lazy[idx]; } st[idx]+=lazy[idx]; lazy[idx]=0; } void update(ll idx,ll l,ll r,ll posl,ll posr,ll val){ prop(idx,l,r); if(l>posr || r<posl)return; //cout<<idx<<" "<<l<<" k"<<r<<endl; if(l>=posl && r<=posr){ lazy[idx]+=val; prop(idx,l,r); } else{ ll mid=(l+r)/2; update(2*idx+1,l,mid,posl,posr,val); update(2*idx+2,mid+1,r,posl,posr,val); st[idx]=max(st[2*idx+1],st[2*idx+2]); } } ll query(ll idx,ll l,ll r,ll posl,ll posr){ prop(idx, l, r); if(l >= posl && r <= posr) return st[idx]; else if(l > posr || r < posl) return 0; else { ll mid = (l + r) / 2; return max(query(2 * idx+1, l, mid, posl, posr) , query(2 * idx + 2, mid + 1, r, posl, posr)); } } ll count_swaps(vector<int> s) { n=s.size(); st=lazy=vector<ll>(4*n+1); deque<ll>pos[2][n+1]; for(ll q=0;q<s.size();q++){ if(s[q]<0){ pos[0][-s[q]].push_back(q); } else{ pos[1][s[q]].push_back(q); } update(0,0,n,q,q,q); } ll ans=0; bool udh[n+1]; memset(udh,false,sizeof udh); ll idx=0; //cout<<query(0,0,n,4,4)<<endl; for(ll q=0;q<s.size();q++){ if(udh[q])continue; if(s[q]<0){ ll hah=pos[1][abs(s[q])].front(); pos[0][abs(s[q])].pop_front(); pos[1][abs(s[q])].pop_front(); udh[hah]=true; ll brp=query(0,0,n,hah,hah); ans+=brp-idx; ans--; update(0,0,n,0,hah,1); //cout<<hah<<" "<<q<<" "<<brp<<endl; } else{ ll hah=pos[0][s[q]].front(); pos[0][s[q]].pop_front(); pos[1][s[q]].pop_front(); udh[hah]=true; ll brp=query(0,0,n,hah,hah); ans+=brp-idx; ans--; update(0,0,n,0,hah,1); ans++; //cout<<hah<<" "<<q<<" "<<brp<<endl; } idx+=2; udh[q]=true; // cout<<ans<<" "<<query(0,0,n,5,5)<<endl; } 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...