Submission #1264806

#TimeUsernameProblemLanguageResultExecution timeMemory
1264806hitsuujArranging Shoes (IOI19_shoes)C++20
10 / 100
21 ms4144 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; #define pb push_back const int lim=1e5; int n; int tri[lim+10]; int seek(int x){ int res=0; while(x<=n){ res+=tri[x]; x+=x&-x; } return res; } void upd(int x){ while(x>0){ tri[x]++; x-=x&-x; } } long long count_swaps(std::vector<int> s) { n=s.size(); map<int,queue<int>>q; vector<int>tan(n); int cnt=1; for(int i=0;i<n;i++) q[s[i]].push(i); for(auto [x,pos]:q){ if(x>0) break; while(pos.size()){ int cur=pos.front(); pos.pop(); int pas=q[-s[cur]].front(); q[-s[cur]].pop(); tan[cur]=cnt; cnt++; tan[pas]=cnt; cnt++; } } int ans=0; for(int i=0;i<n;i++){ ans+=seek(tan[i]); upd(tan[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...