제출 #796831

#제출 시각아이디문제언어결과실행 시간메모리
796831HD1Arranging Shoes (IOI19_shoes)C++14
100 / 100
570 ms151256 KiB
//we are all lost trying to be someone. #include "shoes.h" #include <bits/stdc++.h> #define fastio ios_base::sync_with_stdio(0); cin.tie(0); #define sz(x) ll(x.size()) #define reve(x) reverse(x.begin(),x.end()) #define ff first #define ss second #define pb push_back using namespace std; typedef long long ll; typedef long double ld; const ll MAX=1e6+100; const ll mod=1e9+7; const ll inf=1e9; ll tree[MAX], A[MAX]; ll n=0; map<ll,queue<ll>>M; void build_tree(ll id, ll l, ll r){ if(r-l==1){ tree[id]=l; return; } ll mid=(l+r)/2; build_tree(id*2, l, mid); build_tree(id*2+1, mid, r); return; } void update(ll id, ll l, ll r, ll L, ll R){ if(l>=R or r<=L) return; if(l>=L and r<=R){ tree[id]++; return; } ll mid=(l+r)/2; update(id*2, l, mid, L, R); update(id*2+1, mid, r, L, R); return; } ll ns=0; void query(ll id, ll l, ll r, ll L, ll R){ if(l>=R or r<=L) return; ns+=tree[id]; if(l>=L and r<=R){ return; } ll mid=(l+r)/2; query(id*2, l, mid, L, R); query(id*2+1, mid, r, L, R); return; } ll aport(ll p, ll q, ll x, ll y){ ns=0; query(1, 0,n, p,p+1); M[y].pop(); ll a=ns; ns=0; query(1, 0, n, q, q+1); M[y*-1].pop(); ll b=ns; if(x==1)update(1,0, n,p+1,q); else update(1,0, n,p,q); return b-a; } long long count_swaps(vector<int> c){ n=sz(c); for( ll i=0; i<n ; i++){ M[c[i]].push(i); } ll ans=0; build_tree(1,0, n); for(ll i = 0; i < n; i++){ if(sz(M[c[i]])>0){ if(M[c[i]].front()!=i)continue; ll p=M[c[i]].front(); ll q=M[c[i]*-1].front(); if(c[i]<0){ ans+=aport(p,q,1, c[i])-1; } else{ ans+=aport(p,q,0,c[i]); } } } 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...