제출 #494943

#제출 시각아이디문제언어결과실행 시간메모리
494943luka1234Arranging Shoes (IOI19_shoes)C++14
100 / 100
79 ms13472 KiB
#include "shoes.h" #include<bits/stdc++.h> #define ll long long #define ff first #define ss second using namespace std; int maxn=200001; ll f[200001]; int getsum(int v){ int ans=0; for(int i=v;i>=1;i=(i&(i-1))){ ans+=f[i]; } return ans; } void update(int v,int x){ for(int i=v;i<=maxn;i=2*i-(i&(i-1))){ f[i]+=x; } } long long count_swaps(std::vector<int> s) { int n=s.size()/2; ll ans=0; vector<pair<int,int>> v; vector<pair<int,int>> inde[maxn]; for(int i=0;i<(int)s.size();i++){ inde[abs(s[i])].push_back({s[i],i}); } for(int i=1;i<=n;i++){ sort(inde[i].begin(),inde[i].end()); for(int j=0;j<((int)inde[i].size()/2);j++){ int l=inde[i][j].ss; int r=inde[i][j+((int)inde[i].size()/2)].ss; if(l>r){ swap(l,r); ans++; } v.push_back({l+1,r+1}); } } for(int i=1;i<=2*n;i++) update(i,1); sort(v.begin(),v.end()); for(pair<int,int> i:v){ ans+=getsum(i.ss-1)-getsum(i.ff); update(i.ff,-1); update(i.ss,-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...