제출 #147037

#제출 시각아이디문제언어결과실행 시간메모리
147037DenisovArranging Shoes (IOI19_shoes)C++14
100 / 100
119 ms21236 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long vector <int> t, used; inline static int f (int i) { return i | (i + 1); } inline static int g (int i) { return i & (i + 1); } inline void upd (int i, int x) { for (; i < (int)t.size(); i = f(i)) t[i] += x; } inline int sum (int i) { int res = 0; for (; i >= 0; i = g(i) - 1) res += t[i]; return res; } inline int sum (int l, int r) { return sum(r) - sum(l - 1); } vector<vector <int> > pos; inline int get_pos (int x, int n) { if (pos[-x + n].empty()) { cout << "HOW"; exit(0); } return pos[-x + n].back(); } ll count_swaps(vector<int> a) { ll ans = 0; int n = (int)a.size(); t.resize(n); pos.resize(n + n + 1); used.resize(n + n + 1); for (int i = 0; i < n; i++) { pos[a[i] + n].push_back(i); } for (auto &i : pos) reverse(i.begin(), i.end()); for (int i = 0; i < n; i++) { if (used[a[i] + n] > 0) { --used[a[i] + n]; continue; } int cur = i + sum(i), x = get_pos(a[i], n); int to = x + sum(x); ans += to - cur - 1 + bool(a[i] > 0); upd(i, 1); upd(x, -1); pos[a[i] + n].pop_back(); pos[-a[i] + n].pop_back(); ++used[-a[i] + n]; } 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...