제출 #387476

#제출 시각아이디문제언어결과실행 시간메모리
387476ruadhanArranging Shoes (IOI19_shoes)C++17
100 / 100
77 ms9192 KiB
#include <bits/stdc++.h> typedef long long ll; #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() using namespace std; typedef pair<int, int> pi; const int MAXN = 2e5 + 1; int n; int bit[MAXN]; void upd(int i, int v) { for (; i <= 2 * n; i += i & -i) bit[i] += v; } ll sum(int i) { ll res = 0; for (; i > 0; i -= i & -i) res += bit[i]; return res; } ll count_swaps(vector<int> S) { ll ans = 0; n = sz(S) / 2; vector<pi> swaps; vector<pi> idx[n + 1]; for (int i = 0; i < 2 * n; i++) idx[abs(S[i])].push_back({S[i], i + 1}); for (int i = 1; i <= n; i++) { sort(all(idx[i])); // for (auto x : idx[i]) // cout << x.first << " " << x.second << endl; for (int j = 0; j < sz(idx[i]) / 2; j++) { int l = idx[i][j].second; int r = idx[i][j + sz(idx[i]) / 2].second; if (l > r) { swap(l, r); ans++; } swaps.push_back({l, r}); } } sort(all(swaps)); // for (auto x : swaps) // cout << x.first << " " << x.second << endl; for (int i = 1; i <= 2 * n; i++) upd(i, 1); // cout << "ans = " << ans << endl; for (auto s : swaps) { // ans += sum(s.second - 1) - sum(s.first); ans += sum(s.second - 1) - sum(s.first); upd(s.first, -1); // cout << "s = " << s.first << " " << s.second << endl; upd(s.second, -1); } return ans; } // int main() // { // int t; // cin >> t; // vector<int> S(t * 2); // for (auto &x : S) // cin >> x; // // for (auto x : S) // // cout << x << " "; // // cout << endl; // cout << count_swaps(S) << endl; // return 0; // }
#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...