제출 #145526

#제출 시각아이디문제언어결과실행 시간메모리
145526Sarah_MokhtarArranging Shoes (IOI19_shoes)C++14
0 / 100
2 ms376 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+10,M=(N<<4),OO=0x3f3f3f; int pos[N],tree[M]; void build(int node,int l,int r){ if(l==r) tree[node]=pos[l]; else{ int med=(l+r)/2; build(node<<1,l,med); build(node<<1|1,med+1,r); tree[node]=tree[node<<1]+tree[node<<1|1]; } } void update(int node,int l,int r,int idx,int val){ if(l>r || l>idx || r<idx) return; if(l==r) tree[node]=val; else{ int med=(l+r)/2; update(node<<1,l,med,idx,val); update(node<<1|1,med+1,r,idx,val); tree[node]=tree[node<<1]+tree[node<<1|1]; } } int query(int node,int s,int e,int l,int r){ if(s>e||s>r||e<l) return 0; if(s>=l&&e<=r) return tree[node]; int med=(s+e)/2; int q1=query(2*node,s,med,l,r); int q2=query(2*node+1,med+1,e,l,r); return max(q1,q2); } ll count_swaps(vector<int>s){ map<int,vector<int>>m; ll ret=0; int n=s.size(); for(int i=0;i<n;++i) update(1,0,n-1,i,1); for(int i=n-1;i>=0;--i) m[s[i]].push_back(i); for(int i=0;i<n;++i){ if(query(1,0,n-1,0,i)-query(1,0,n-1,0,i-1)!=1) continue; int k=m[-s[i]].back(); m[s[i]].pop_back(); m[-s[i]].pop_back(); update(1,0,n-1,i,-1); update(1,0,n-1,k,-1); ret+=query(1,0,n-1,0,k)-query(1,0,n-1,0,i); if(s[i]>0) ++ret; } return ret; }
#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...