Submission #1208335

#TimeUsernameProblemLanguageResultExecution timeMemory
1208335GabpArranging Shoes (IOI19_shoes)C++20
0 / 100
0 ms328 KiB
#include<bits/stdc++.h> using namespace std; long long int count_swaps(vector<int> S) { int n = S.size() / 2; int cnt = 0; vector<int> idx(n + 1, -1); for (int i = 0; i < 2 * n; i++) { int x = abs(S[i]); if (idx[x] != -1) { S[i] = 2 * idx[x] + (S[i] > 0); } idx[x] = cnt++; S[i] = 2 * cnt - 2 + (S[i] < 0); } long long int ans = 0; auto solve = [&](auto self, int l, int r) -> void { if (l == r) return; int mid = l + (r - l) / 2; self(self, l, mid); self(self, mid + 1, r); int p1 = l, p2 = mid + 1; vector<int> a; while (p1 <= mid || p2 <= r) { if (p1 > mid) a.push_back(S[p2++]); else if (p2 > r) a.push_back(S[p1++]); else if (S[p1] < S[p2]) a.push_back(S[p1++]); else { a.push_back(S[p2++]); ans += mid + 1 - p1; } } for (int i = l; i <= r; i++) S[i] = a[i - l]; }; solve(solve, 0, 2 * n - 1); 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...