Submission #1093246

#TimeUsernameProblemLanguageResultExecution timeMemory
1093246emptypringlescanArranging Shoes (IOI19_shoes)C++17
100 / 100
98 ms72912 KiB
#include <bits/stdc++.h> using namespace std; long long fenw[200005]; void update(int x){ for(;x<200005;x+=x&-x) fenw[x]++; } long long query(int x){ long long ret=0; for(;x;x-=x&-x) ret+=fenw[x]; return ret; } long long count_swaps(vector<int> arr){ int n=arr.size()/2; int corr[n*2]; queue<int> prev[n+5]; for(int i=0; i<n*2; i++){ if(prev[abs(arr[i])].empty()||(prev[abs(arr[i])].front()<0&&arr[i]<0)||(prev[abs(arr[i])].front()>0&&arr[i]>0)){ if(arr[i]<0) prev[abs(arr[i])].push(-i-1); else prev[abs(arr[i])].push(i+1); } else{ //cout << prev[abs(arr[i])].front() << ' ' << arr[i] << '\n'; corr[abs(prev[abs(arr[i])].front())-1]=i; corr[i]=abs(prev[abs(arr[i])].front())-1; prev[abs(arr[i])].pop(); } } //for(int i=0; i<n*2; i++) cout << corr[i] << ' '; long long ans=0; for(int i=0; i<n*2; i++){ if(corr[i]<i) continue; ans+=corr[i]-i-(query(corr[i])-query(i)); if(arr[i]<0) ans--; update(corr[i]); } 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...