제출 #314511

#제출 시각아이디문제언어결과실행 시간메모리
314511jaaguptammeArranging Shoes (IOI19_shoes)C++14
0 / 100
10 ms12800 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll N=400005; vector<ll>ar(N,0); ll get(int p){ ll ans=0; while(p){ ans+=ar[p]; p-=p&(-p); } return ans; } void add(int p,ll val){ while(p<N){ ar[p]+=val; p+=p&(-p); } } long long count_swaps(std::vector<int> s) { vector<pair<int,int>>g[N]; int n=s.size()/2; for(int i=1;i<=2*n;i++){ int ps=i-1; g[abs(s[ps])].push_back({s[ps],i}); add(i,1); } ll ans=0; vector<pair<int,int>>ns; for(int i=1;i<N;i++){ sort(g[i].begin(),g[i].end()); int cnt=g[i].size()/2; for(int j=0;j<cnt;j++){ int l=g[i][j].second; int r=g[i][j+cnt].second; if(l>r){ ans++; swap(l,r); } ns.push_back({l,r}); } } for(auto el:ns){ int l=el.first,r=el.second; ans+=get(r-1)+get(l); add(l,-1);add(r,-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...