제출 #921414

#제출 시각아이디문제언어결과실행 시간메모리
921414AverageAmogusEnjoyerArranging Shoes (IOI19_shoes)C++17
50 / 100
108 ms48340 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; } template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; } constexpr int nax = 100100; int st[4*nax]; int n; void upd(int p,int u=1,int tl=1,int tr=n) { if (tl == tr) { st[u] = 1; return; } int mid=(tl+tr)/2; if (p<=mid) { upd(p,2*u,tl,mid); } else { upd(p,2*u+1,mid+1,tr); } st[u] = st[2*u]+st[2*u+1]; } int qry(int l,int r,int u=1,int tl=1,int tr=n) { if (l > r) { return 0; } if (l == tl && r == tr) { return st[u]; } int mid = (tl+tr)/2; return qry(l,min(mid,r),2*u,tl,mid)+qry(max(mid+1,l),r,2*u+1,mid+1,tr); } ll count_swaps(vector<int> a) { ll ans = 0; n = (int)a.size(); map<int,vector<int>> p; for (int i=n-1;i>=0;i--) { p[a[i]].push_back(i); } vector<bool> done(n); for (int i=0;i<n;i++) { if (done[i]) { continue; } done[i] = true; assert(!p[-a[i]].empty()); int nxt = p[-a[i]].back(); done[nxt] = true; p[-a[i]].pop_back(); assert(!p[a[i]].empty() && p[a[i]].back() == i); p[a[i]].pop_back(); int add = max(0,nxt-(i+1)-qry(i+1,nxt)); // cout << add << " "; ans += add; if (a[i] > 0) { ans++; // cout << "added 1 "; } // cout << ans << endl; upd(nxt); } 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...