Submission #1203261

#TimeUsernameProblemLanguageResultExecution timeMemory
1203261SpyrosAlivArranging Shoes (IOI19_shoes)C++20
100 / 100
117 ms15560 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long int n; vector<int> a; class Segtree { private: int n; vector<int> seg; void update(int node, int l, int r, int idx) { if (l == r) seg[node] = 1; else { int mid = (l + r) / 2; if (idx <= mid) update(node*2+1, l, mid, idx); else update(node*2+2, mid+1, r, idx); seg[node] = seg[node*2 + 1] + seg[node*2 + 2]; } } int query(int node, int start, int end, int l, int r) { if (start > r || end < l) return 0; else if (start >= l && end <= r) return seg[node]; else { int mid = (start + end) / 2; return query(node*2+1, start, mid, l, r) + query(node*2+2, mid+1, end, l, r); } } public: void init(int nn) { n = nn; seg.assign(n*4, 0); } void update(int idx) { update(0, 0, n-1, idx); } int query(int l, int r) { if (l > r) return 0; return query(0, 0, n-1, l, r); } } seg; int get_dis(int pos, int a, int b) { a += seg.query(a+1, (2*n)-1); b += seg.query(b+1, (2*n)-1); int bon = a > b; return abs(a - pos) + abs((b + bon) - (pos + 1)); } ll count_swaps(vector<int> s) { n = s.size(); seg.init(n); a = s; int c = 0; vector<int> r(n/2, 0), l(n/2, 0); vector<vector<int>> poss(n+1); for (int i = 0; i < n; i++) { poss[abs(s[i])].push_back(i); } for (int i = 1; i <= n; i++) { vector<int> L, R; for (auto j: poss[i]) { if (abs(s[j]) != i) continue; if (s[j] < 0) L.push_back(j); else R.push_back(j); } int sz = L.size(); for (int j = 0; j < sz; j++) { l[c] = L[j]; r[c] = R[j]; c++; } } n /= 2; vector<pair<int, int>> ord; for (int i = 0; i < n; i++) { ord.push_back({get_dis(0, l[i], r[i]), i}); } ll ans = 0; sort(ord.begin(), ord.end()); int pos = 0; for (auto [u, v]: ord) { ans += get_dis(pos, l[v], r[v]); seg.update(l[v]); seg.update(r[v]); pos += 2; } 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...