제출 #540537

#제출 시각아이디문제언어결과실행 시간메모리
540537__VariattoArranging Shoes (IOI19_shoes)C++17
0 / 100
18 ms19452 KiB
//#include "shoes.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define fi first #define se second #define ll long long const ll MAX=2e5+10, S=1<<19; ll n, curr, licz[MAX], x[MAX], licz2[MAX]; bool odw[MAX]; vector<ll>wie[MAX], mnie[MAX]; ll t[2*S+10]; void Insert(ll v){ v+=S; while(v){ t[v]++; v/=2; } } ll Query(ll a, ll b){ ll w=0; a+=S-1, b+=S+1; while(a+1<b){ if(a%2==0) w+=t[a+1]; if(b%2==1) w+=t[b-1]; a/=2, b/=2; } return w; } ll a[MAX]; ll count_swaps(vector<int>xx){ n=xx.size()/2; for(ll i=1; i<=2*n; i++){ curr=xx[i-1]; if(curr>0) wie[curr].pb(i); else mnie[-curr].pb(i); a[i]=curr; } ll akt=0; for(ll i=1; i<=2*n; i++){ curr=a[i]; if(odw[i]) continue; if(curr<0) x[i]=akt*2, x[wie[-curr][licz[-curr]++]]=akt*2+1, odw[wie[-curr][licz[-curr]++]]=true; else x[i]=akt*2+1, x[mnie[curr][licz2[curr]++]]=akt*2, odw[mnie[curr][licz2[curr]++]]=true; akt++; } ll wyn=0; for(ll i=1; i<=2*n; i++){ wyn+=Query(x[i]+1, S-1); Insert(x[i]); } return wyn; } /*int main(){ ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0); int nn; cin>>nn; vector<int>xd; for(int i=1; i<=nn; i++){ int curr; cin>>curr; xd.pb(curr); } cout<<count_swaps(xd)<<"\n"; }*/
#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...