제출 #1203129

#제출 시각아이디문제언어결과실행 시간메모리
1203129SpyrosAlivArranging Shoes (IOI19_shoes)C++20
10 / 100
0 ms328 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; update(node*2+1, l, mid, idx); 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; }
#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...