제출 #292944

#제출 시각아이디문제언어결과실행 시간메모리
292944HemimorArranging Shoes (IOI19_shoes)C++14
100 / 100
181 ms17164 KiB
#include "shoes.h" #include <algorithm> #include <iostream> #include <iomanip> #include <numeric> #include <vector> #include <cmath> #include <queue> #include <set> #include <map> using namespace std; typedef long long ll; typedef pair<int,int> P; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<P> vp; typedef vector<vp> vvp; class Segment_Tree{ private: int n; vi date; public: Segment_Tree(int n_){ n=1; while(n<n_) n*=2; date=vi(2*n-1); } void Update(int k,int x){ k+=n-1; date[k]+=x; while(k>0){ k=(k-1)/2; date[k]=date[k*2+1]+date[k*2+2]; } } int Query(int a,int b){ a+=n-1;b+=n-1; int m=0; while(a<b){ if(a%2==0) m+=date[a++]; if(b%2==0) m+=date[--b]; a/=2;b/=2; } return m; } int Open(int k){return date[k+n-1];} }; ll count_swaps(vi a){ ll n=(int)a.size()/2,res=0; vvi bl(n+1),br(n+1); vp c; for(int i=0;i<2*n;i++){ if(a[i]<0) bl[abs(a[i])].push_back(i); else br[abs(a[i])].push_back(i); } for(int i=1;i<=n;i++){ int m=bl[i].size(); for(int j=0;j<m;j++){ int l=bl[i][j],r=br[i][j]; if(l>r){ res++; swap(l,r); } c.push_back({l,r}); } } sort(c.begin(),c.end()); Segment_Tree st(2*n); for(auto p:c){ int l=p.first,r=p.second; res+=st.Query(l,r); res+=st.Query(r,2*n)*2; st.Update(r,1); } 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...