제출 #304726

#제출 시각아이디문제언어결과실행 시간메모리
304726kjain_1810Arranging Shoes (IOI19_shoes)C++17
25 / 100
247 ms139512 KiB
#include "shoes.h" #include<bits/stdc++.h> typedef long long ll; using namespace std; const int N = 1e5 + 5; int n; ll segt[8 * N]; queue<int>vec[2 * N]; inline int lt(int x){return 2 * x;} inline int rt(int x){return 2 * x + 1;} void upd(int nd, int s, int e, int idx) { if(s > idx || e < idx) return; if(s == e) { segt[nd] += 1; return; } int m = (s + e) / 2; upd(lt(nd), s, m, idx); upd(rt(nd), m + 1, e, idx); segt[nd] = segt[lt(nd)] + segt[rt(nd)]; } ll query(int nd, int s, int e, int l, int r) { if(s > r || e < l) return 0; if(s >= l && e <= r) return segt[nd]; int m = (s + e) / 2; return query(lt(nd), s, m, l, r) + query(rt(nd), m + 1, e, l, r); } long long count_swaps(vector<int> s) { ll ans = 0; n = s.size(); for(int a = 0; a < n; a++){ s[a] += n / 2; vec[s[a]].push(a); } for(int a = 0; a < n; a++) { if(query(1, 1, n, a, a) == 1) continue; int target; if(s[a] > n) target = (-(s[a] - n / 2) + n / 2); else target = (-(s[a] - n / 2) + n / 2); int idx = vec[target].front(); vec[target].pop(); vec[s[a]].pop(); ll toadd; if(s[a] < target) toadd = (idx - a - 1 - query(1, 1, n, a, idx)); else toadd = (idx - a - query(1, 1, n, a, target)); ans += toadd; // printf("%d %d %d %d %lld\n", a, s[a], target, idx, toadd); upd(1, 1, n, idx); } 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...