제출 #1054723

#제출 시각아이디문제언어결과실행 시간메모리
1054723RecursiveCoArranging Shoes (IOI19_shoes)C++17
100 / 100
67 ms17468 KiB
#include <bits/stdc++.h> using namespace std; vector<int> tree; void upd(int v, int i, int l, int r) { if (l == r) tree[v]++; else { int middle = (l + r) / 2; if (i <= middle) upd(2 * v, i, l, middle); else upd(2 * v + 1, i, middle + 1, r); tree[v] = tree[2 * v] + tree[2 * v + 1]; } } int query(int v, int ql, int qr, int l, int r) { if (ql <= l && r <= qr) return tree[v]; if (r < ql || qr < l) return 0; int middle = (l + r) / 2; int left = query(2 * v, ql, qr, l, middle); int right = query(2 * v + 1, ql, qr, middle + 1, r); return left + right; } long long count_swaps(vector<int> nums) { int n = nums.size() / 2; vector<vector<int>> left(n + 1); vector<vector<int>> right(n + 1); for (int i = 0; i < 2 * n; i++) { if (nums[i] < 0) left[-nums[i]].push_back(i); else right[nums[i]].push_back(i); } vector<pair<int, int>> segs; long long ans = 0; for (int i = 0; i <= n; i++) { int s = left[i].size(); for (int j = 0; j < s; j++) { int l = left[i][j]; int r = right[i][j]; if (l > r) { ans++; swap(l, r); } segs.push_back({l, r}); } } sort(segs.begin(), segs.end()); vector<int> arr(2 * n); for (int i = 0; i < n; i++) { arr[segs[i].first] = i; arr[segs[i].second] = i; } tree.resize(4 * n, 0); for (int i = 0; i < 2 * n; i++) { int val = arr[i]; int add = val == n - 1? 0: query(1, val + 1, n - 1, 0, n - 1); ans += (long long) add; upd(1, val, 0, 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...