제출 #395502

#제출 시각아이디문제언어결과실행 시간메모리
395502luisgalanArranging Shoes (IOI19_shoes)C++14
100 / 100
364 ms278620 KiB
#include<bits/stdc++.h> #include "shoes.h" using namespace std; typedef long long int ll; const int MAX_N = ll(2e5 + 3); ll st[4 * MAX_N]; void build(int p, int tl, int tr) { if (tl == tr) { st[p] = 0; return; } int m = (tl + tr) / 2; build(2*p, tl, m); build(2*p+1, m+1, tr); st[p] = st[2*p] + st[2*p+1]; } ll query(int p, int tl, int tr, int l, int r) { if (l > r) return 0; if (tl == l && tr == r) { return st[p]; } int m = (tl + tr) / 2; ll L = query(2*p, tl, m, l, min(r, m)); ll R = query(2*p+1, m+1, tr, max(l, m+1), r); return L + R; } void update(int p, int tl, int tr, int k, ll v) { if (tl == tr) { st[p] = v; return; } int m = (tl + tr) / 2; if (k <= m) { update(2*p, tl, m, k, v); } else { update(2*p+1, m+1, tr, k, v); } st[p] = st[2*p] + st[2*p+1]; } ll count_swaps(vector<int> s) { int n = s.size(); vector<int> taken(n); vector<queue<int>> neg(n + 1); vector<queue<int>> pos(n + 1); vector<int> pairs(n); // make pairs for (int i = 0; i < n; i++) { if (s[i] < 0) { if (!pos[-s[i]].empty()) { pairs[pos[-s[i]].front()] = i; pos[-s[i]].pop(); } else { neg[-s[i]].push(i); } } else { if (!neg[s[i]].empty()) { pairs[neg[s[i]].front()] = i; neg[s[i]].pop(); } else { pos[s[i]].push(i); } } } build(1, 0, n-1); ll ans = 0; for (int i = 0; i < n; i++) { if (taken[i]) continue; int j = pairs[i]; ans += j - i - query(1, 0, n-1, i, j); if (s[i] < 0) ans--; taken[i] = true; taken[j] = true; update(1, 0, n-1, i, taken[i]); update(1, 0, n-1, j, taken[j]); } return ans; } // queue for each shoe size // use queue to find best pairs // use something like a segtree to find number of swaps for each pair
#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...