제출 #784998

#제출 시각아이디문제언어결과실행 시간메모리
784998HD1Arranging Shoes (IOI19_shoes)C++14
50 / 100
507 ms149260 KiB
//we are all lost trying to be someone. #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 int ll; typedef long double ld; const ll MAX=1e7+100; const ll mod=1e9+7; const ll inf=1e9; ll tree[MAX], A[MAX]; 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; } long long count_swaps(vector<int> c){ for( ll i=0; i<sz(c) ; i++){ M[c[i]].push(i); } ll ans=0; build_tree(1,0, sz(c)); for(ll i = 0; i < sz(c); i++){ if(sz(M[c[i]])>0){ if(M[c[i]].front()!=i)continue; if(c[i]<0){ ns=0; ll p=M[c[i]].front(); query(1, 0,sz(c), p,p+1); M[c[i]].pop(); ll a=ns; ns=0; ll q=M[c[i]*-1].front(); ns=0; query(1, 0, sz(c), q, q+1); M[c[i]*-1].pop(); ll b=ns; ans+=b-a-1; update(1,0, sz(c),p,q); } else{ ns=0; ll p=M[c[i]].front(); query(1, 0,sz(c), p,p+1); M[c[i]].pop(); ll a=ns; ns=0; ll q=M[c[i]*-1].front(); ns=0; query(1, 0, sz(c), q, q+1); M[c[i]*-1].pop(); ll b=ns; ans+=b-a; update(1,0, sz(c),p,q); } } } 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...