Submission #1264889

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