제출 #867493

#제출 시각아이디문제언어결과실행 시간메모리
867493cheat_when_I_was_youngArranging Shoes (IOI19_shoes)C++17
10 / 100
79 ms75408 KiB
#include "shoes.h" #include "bits/stdc++.h" using namespace std; void update(int pos, int val, vector<int> &bit) { ++pos; for (; pos < (int)bit.size(); pos += pos&-pos) bit[pos] += val; } void range_update(int l, int r, int val, vector<int> &bit) { update(l, val, bit); update(r+1, val, bit); } int get(int pos, vector<int> &bit) { ++pos; int res = 0; for (; pos > 0; pos -= pos&-pos) res += bit[pos]; return res; } long long count_swaps(vector<int> s) { int n = (int)s.size(); long long ans = 0; vector<int> bit(n+1, 0); vector<vector<int>> l(n/2+1, vector<int>()); vector<queue<int>> r(n/2+1, queue<int>()); for (int i = 0; i < n; ++i) { if (s[i] < 0) { s[i] = -s[i]; if (r[s[i]].size()) { ans += i - r[s[i]].front() - get(r[s[i]].front(), bit); range_update(r[s[i]].front(), i, 1, bit); r[s[i]].pop(); } else l[s[i]].push_back(i); } else { if (l[s[i]].size()) { ans += i - l[s[i]].back() - get(l[s[i]].back(), bit) - 1; range_update(l[s[i]].front(), i, 1, bit); l[s[i]].pop_back(); } else r[s[i]].push(i); } } return ans; } void solve() { cout << count_swaps({1, 1, 1, -1, -1, -1}); }
#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...