제출 #863405

#제출 시각아이디문제언어결과실행 시간메모리
86340520163070Arranging Shoes (IOI19_shoes)C++14
100 / 100
49 ms21504 KiB
#include <bits/stdc++.h> #include "shoes.h" using namespace std; const int N=4e5+10; int n; int tr[N]; int vis[N]; int a[N]; vector<int> pos[N]; int lowbit(int x) { return x&-x; } int sum(int x) { int res=0; for(int i=x;i;i-=lowbit(i)) res+=tr[i]; return res; } void add(int x,int c) { for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c; } long long count_swaps(std::vector<int> s) { n=s.size(); for(int i=0;i<n;i++) a[i+1]=s[i]; for(int i=1;i<=n;i++) { pos[a[i]+n].push_back(i); add(i,1); } long long ans=0; for(int i=n;i>=1;i--) { if(vis[i]) continue; vis[i]=1; pos[a[i]+n].pop_back(); int res=pos[n-a[i]].back(); pos[n-a[i]].pop_back(); vis[res]=1; ans=ans+(long long)(sum(i-1)-sum(res))+((a[i]<0)?1:0); add(res,-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...