제출 #550272

#제출 시각아이디문제언어결과실행 시간메모리
550272pere_gilArranging Shoes (IOI19_shoes)C++14
50 / 100
113 ms50576 KiB
#include "shoes.h" #include "bits/stdc++.h" using namespace std; #define index int med=(s+e)/2,l=2*n+1,r=2*n+2 typedef long long ll; const int tam=1e5; unordered_map<int,priority_queue<int,vector<int>,greater<int>>> ma; vector<int> tr(4*tam); void init(int n, int s, int e){ if(s==e){ tr[n]=1; return; } index; init(l,s,med); init(r,med+1,e); tr[n]=tr[l]+tr[r]; } void update(int n, int s, int e, int pos, vector<int> &v){ if(s==e){ v[s]=0; tr[n]=0; return; } index; if(pos<=med) update(l,s,med,pos,v); else update(r,med+1,e,pos,v); tr[n]=tr[l]+tr[r]; } int query(int n, int s, int e, int i, int j){ if(i>j) return 0; if(i<=s && e<=j) return tr[n]; index; if(j<=med) return query(l,s,med,i,j); if(i>med) return query(r,med+1,e,i,j); return query(l,s,med,i,j)+query(r,med+1,e,i,j); } long long count_swaps(std::vector<int> s) { int n=s.size(); for(int i=0;i<n;i++) ma[s[i]].push(i); init(0,0,n-1); ll res=0; vector<bool> vis(n,false); for(int i=0;i<n;i++){ if(vis[i]) continue; int j=ma[-s[i]].top(); ma[-s[i]].pop(); ma[s[i]].pop(); vis[j]=true; int moves=query(0,0,n-1,i+1,j-1)+(s[i]>0); res+=moves; update(0,0,n-1,j,s); } return res; }
#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...