Submission #1203134

#TimeUsernameProblemLanguageResultExecution timeMemory
1203134SpyrosAlivArranging Shoes (IOI19_shoes)C++20
45 / 100
50 ms6948 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: Segtree(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); } }; ll count_swaps(vector<int> s) { n = s.size(); a = s; Segtree seg(n); vector<int> l, r; for (int i = 0; i < n; i++) { if (s[i] < 0) l.push_back(i); else r.push_back(i); } reverse(l.begin(), l.end()); reverse(r.begin(), r.end()); ll ans = 0; for (int i = 0; i < n; i++) { int curr = 0; if (i % 2 == 0) { curr = l.back(); l.pop_back(); } else { curr = r.back(); r.pop_back(); } int nxt = curr + seg.query(curr+1, n-1); ans += abs(nxt - i); seg.update(curr); } return ans; } /* int main() { int n; cin >> n; vector<int> arr; for (int i = 0; i < n; i++) { int x; cin >> x; arr.push_back(x); } cout << count_swaps(arr) << "\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...