Submission #645921

#TimeUsernameProblemLanguageResultExecution timeMemory
645921GaLzArranging Shoes (IOI19_shoes)C++14
100 / 100
239 ms274216 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<ll> vll; const ll mod=1e9+7; const ll maxn=2e5+5; #define ok ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define fi first #define se second #define pb push_back #define ub upper_bound #define lb lower_bound #define endl '\n' int n, fen[maxn], sm, pos, cnt; queue<int> qul[maxn], qur[maxn]; bool use[maxn]; void add(int bit) { for(; bit<=n; bit+=bit&(-bit)) fen[bit]++; } int get(int bit) { int res=0; for(; bit>0; bit-=bit&(-bit)) res+=fen[bit]; return res; } ll count_swaps(vector<int> v) { n=(int)v.size(); ll ans=0; for(int i=0; i<n; i++) { if(v[i]<0) qul[-1*v[i]].push(i+1); else qur[v[i]].push(i+1); } for(int i=0; i<n; i++) { if(use[i+1]) continue; if(v[i]<0) { sm=-1*v[i]; pos=qur[sm].front(); cnt=get(pos)-get(i+1); qur[sm].pop(); qul[sm].pop(); int range=pos-(i+1)-1-cnt; ans+=range; add(pos); use[pos]=1; } else { pos=qul[v[i]].front(); cnt=get(pos)-get(i+1); qur[v[i]].pop(); qul[v[i]].pop(); int range=pos-(i+1)-cnt; ans+=range; add(pos); use[pos]=1; } } 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...