제출 #1021749

#제출 시각아이디문제언어결과실행 시간메모리
1021749nisanduuArranging Shoes (IOI19_shoes)C++14
0 / 100
0 ms348 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; void update(vector<ll>&seg,ll ind,ll l,ll r,ll givenpos){ if(l==r){ seg[ind]+=1; return; } ll mid = l + (r-l)/2; if(mid>=givenpos){ update(seg,2*ind+2,mid+1,r,givenpos); }else{ update(seg,2*ind+1,l,mid,givenpos); } seg[ind] = seg[2*ind+1] + seg[2*ind+2]; return; } ll query(vector<ll>&seg,ll ind,ll l,ll r,ll left,ll right){ if(l>right||r<left) return 0; if(l<=left&&r>=right) return seg[ind]; ll mid = l + (r-l)/2; return query(seg,2*ind+1,l,mid,left,right) + query(seg,2*ind+2,mid+1,r,left,right); } long long count_swaps(std::vector<int> s) { long long ans = 0; long long n = s.size(); vector<vector<ll>> left(n+10),right(n+10); for(ll i=0;i<n;i++){ ll sz = abs(s[i]); if(s[i]<0){ left[sz].push_back(-i); }else{ right[sz].push_back(-i); } } for(ll i=0;i<n;i++){ sort(left[i].begin(),left[i].end()); sort(right[i].begin(),right[i].end()); } vector<ll> seg(6*n); map<ll,ll> used; for(ll i=0;i<n;i++){ if(!used[i]){ ll sz = abs(s[i]); ll tmpA = 0; if(s[i]<0){ ll pos = right[sz].back(); pos *= -1; right[sz].pop_back(); left[sz].pop_back(); ll am = pos - i; am = am - query(seg,0,0,n-1,i,pos); update(seg,0,0,n-1,pos); used[pos]=1; used[i]=1; tmpA = am; }else{ ll pos = left[sz].back(); pos *= -1; right[sz].pop_back(); left[sz].pop_back(); ll am = pos - i; am = am - query(seg,0,0,n-1,i,pos); update(seg,0,0,n-1,pos); used[pos]=1; used[i]=1; tmpA = am; } if(i%2==0){ if(s[i]>0) tmpA++; }else{ if(s[i]<0) tmpA++; } ans+=tmpA; } } 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...