Submission #1261035

#TimeUsernameProblemLanguageResultExecution timeMemory
1261035motionArranging Shoes (IOI19_shoes)C++20
50 / 100
373 ms148364 KiB
#include<bits/stdc++.h> using namespace std; vector<int> segtree; int len; void SET(int ind, int val) { ind += len; segtree[ind] = val; for (; ind > 1; ind /= 2) { segtree[ind / 2] =segtree[ind] + segtree[ind ^ 1]; } } int range_sum(int start, int e) { int sum = 0; for (start += len, e += len; start < e; start /= 2, e /= 2) { if (start % 2 == 1) { sum+=segtree[start++]; } if (e % 2 == 1) { sum+=segtree[--e]; } } return sum; } int count_swaps(vector<int> S) { int n=S.size(); long long ans=0; vector<int> vis(n,-1); len=n; segtree=vector<int>(len*2,0); map<int,queue<int>> mapa; for(int i=0;i<n;i++) { if(mapa[-S[i]].empty()) { mapa[S[i]].push(i); } else { int curr=mapa[-S[i]].front(); mapa[-S[i]].pop(); vis[curr]=i; } } for(int i=0;i<n;i++) { if(vis[i]==-1) continue; ans+=vis[i]-i-1+range_sum(i,vis[i]); SET(i,1); SET(vis[i],-1); if(S[i]>0) ans+=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...