제출 #535415

#제출 시각아이디문제언어결과실행 시간메모리
535415mario05092929Arranging Shoes (IOI19_shoes)C++14
100 / 100
235 ms142220 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; int n,cnt,g; int a[200005],c[200005],t[800005]; queue <int> wi[200005]; int query(int x,int l,int r,int rl,int rr) { if(rl > r||l > rr) return 0; if(rl <= l&&r <= rr) return t[x]; int mid = (l + r) >> 1; return query(x*2,l,mid,rl,rr)+query(x*2+1,mid+1,r,rl,rr); } void update(int x,int l,int r,int wi) { if(wi < l||r < wi) return; if(l == r) { t[x] = 1; return; } int mid = (l + r) >> 1; update(x*2,l,mid,wi), update(x*2+1,mid+1,r,wi); t[x] = t[x*2]+t[x*2+1]; } ll count_swaps(vector <int> s) { n = s.size(); n /= 2; for(int i = 1;i <= 2*n;i++) a[i] = s[i-1]; for(int i = 1;i <= 2*n;i++) { wi[a[i]+n].push(i); } ll ans = 0; for(int i = 1;i <= 2*n;i++) { if(c[i]) continue; int x = a[i]; //cout << i << ' ' << wi[-x+n].front() << '\n'; if(x < 0) { ans += wi[-x+n].front()-i-query(1,1,2*n,i+1,wi[-x+n].front())-1; } else { ans += wi[-x+n].front()-i-query(1,1,2*n,i+1,wi[-x+n].front()); } update(1,1,2*n,wi[-x+n].front()); update(1,1,2*n,i); c[i] = c[wi[-x+n].front()] = 1; wi[-x+n].pop(); wi[x+n].pop(); } 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...