제출 #1064024

#제출 시각아이디문제언어결과실행 시간메모리
1064024TlenekWodoruArranging Shoes (IOI19_shoes)C++14
100 / 100
70 ms15712 KiB
#include<bits/stdc++.h> #include "shoes.h" using namespace std; int miejsce[100009][2]; vector<int>V1[100009],V2[100009]; int Tre[1000000]; int base; void Przedzial(int l, int p, int dod) { l+=base; p+=base; while(l<=p) { if(l%2==1) { Tre[l]+=dod; l++; } if(p%2==0) { Tre[p]+=dod; p--; } l>>=1; p>>=1; } } int Punkt(int v) { v+=base; int wynik=0; while(v>0) { wynik+=Tre[v]; v>>=1; } return wynik; } int TworzenieDrzewa(int x) { int u=1; while(x>0) { x>>=1; u<<=1; } return u; } long long count_swaps(vector<int>tab) { long long wynik=0; const int n=tab.size(); const int n2=n/2; for(int i=0;i<n;i++) { if(tab[i]<0) { V1[-tab[i]].push_back(i); } else if(tab[i]>0) { V2[tab[i]].push_back(i); } } for(int i=1;i<=n2;i++) { reverse(V1[i].begin(),V1[i].end()); reverse(V2[i].begin(),V2[i].end()); } base=TworzenieDrzewa(n); for(int i=0;i<n;i++) { Tre[i+base]=i; } for(int i=0;i<n;i++) { const int u=abs(tab[i]); if(tab[i]<0&&(int)V1[u].size()>0&&V1[u].back()==i) { int u1=Punkt(V1[u].back()); int u2=Punkt(V2[u].back()); Przedzial(0,V2[u].back(),1); wynik+=u2-u1-1; } else if(tab[i]>0&&(int)V2[u].size()>0&&V2[u].back()==i) { int u1=Punkt(V2[u].back()); int u2=Punkt(V1[u].back()); Przedzial(0,V1[u].back(),1); wynik+=u2-u1; } else{continue;} V1[u].pop_back(); V2[u].pop_back(); } return wynik; }
#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...