제출 #151507

#제출 시각아이디문제언어결과실행 시간메모리
151507outsiderArranging Shoes (IOI19_shoes)C++14
100 / 100
828 ms148876 KiB
#include <bits/stdc++.h> #include "shoes.h" #define ll int #define x first #define y second using namespace std; ll n; vector<ll>a; vector<ll>fn; void update(ll x, ll y){ ll f = x; while(f <= n){ fn[f]+=y; f =f|(f+1); } } ll sum(ll x){ ll num = 0; ll f = x; while(f >= 0){ num += fn[f]; f=(f&(f+1))-1; } return num; } long long count_swaps(vector<int> s) { n=s.size(); a.resize(n+1,1); fn.resize(n+1); for (int i=0;i<=n;i++) update(i,1); map<ll,deque<ll> >mp; for (int i=0;i<n;i++) mp[s[i]].push_back(i); long long ans=0; for (ll i=0;i<n;i++) { if (a[i]==0) continue; ll p=mp[-s[i]].front(); mp[-s[i]].pop_front(); mp[s[i]].pop_front(); update(p,-1); update(i,-1); a[i]=a[p]=0; ans+=sum(p)-sum(i); if (s[i]>0)ans++; } 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...