Submission #751212

#TimeUsernameProblemLanguageResultExecution timeMemory
751212kusmetliqArranging Shoes (IOI19_shoes)C++14
10 / 100
253 ms76732 KiB
#include "shoes.h" #include<bits/stdc++.h> using namespace std; long long fen[200000]; void upd(int x,int v) { x++; if(x==0)return; while(x<200000) { fen[x]+=v; x+=x&(-x); } } long long ask(int x) { x++; long long sum=0; while(x>0) { sum+=fen[x]; x-=x&(-x); } return sum; } long long count_swaps(vector<int> s) { int n=s.size(); map<int,deque<int>>m; for(int i=0;i<n;i++) { upd(i,1); if(s[i]>0) { m[s[i]].push_back(i); } } long long ans=0; for(int i=0;i<n;i++) { if(s[i]<0) { int v=-s[i]; upd(i,-1); ans+=ask(i); int ind=m[v].front(); m[v].pop_front(); upd(ind,-1); ans+=ask(ind); } } 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...