제출 #702008

#제출 시각아이디문제언어결과실행 시간메모리
702008bebraArranging Shoes (IOI19_shoes)C++17
0 / 100
1 ms300 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; using ll = long long; #define dbg(x) cerr << #x << ": " << x << endl; struct FenwickTree { vector<int> tree; int size; FenwickTree(int n) { size = n; tree.resize(size); } void update(int pos, int value) { for (int i = pos; i < size; i |= i + 1) { tree[i] += value; } } ll query(int l, int r) { ll res = 0; for (int i = r; i >= 0; i = (i & (i + 1)) - 1) { res += tree[i]; } for (int i = l - 1; i >= 0; i = (i & (i + 1)) - 1) { res -= tree[i]; } return res; } }; ll count_swaps(vector<int> a) { int n = a.size() / 2; vector<vector<int>> left_elms(n + 1), right_elms(n + 1); for (int i = 0; i < n * 2; ++i) { int x = a[i]; if (x < 0) { left_elms[-x].push_back(i); } else { right_elms[x].push_back(i); } } vector<pair<int, int>> pairs; for (int x = 1; x <= n; ++x) { for (int i = 0; i < (int)left_elms[x].size(); ++i) { pairs.emplace_back(left_elms[x][i], right_elms[x][i]); } } sort(pairs.begin(), pairs.end()); vector<int> p(n * 2); for (int i = 0; i < n; ++i) { auto [x, y] = pairs[i]; p[x] = i; p[y] = i + 1; } ll res = 0; FenwickTree tree(n * 2); for (auto x : p) { res += tree.query(x + 1, n - 1); tree.update(x, 1); } return res; } // int main() { // int n; // cin >> n; // vector<int> a(n); // for (auto& x : a) { // cin >> x; // } // cout << count_swaps(a) << '\n'; // }
#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...