Submission #167943

#TimeUsernameProblemLanguageResultExecution timeMemory
167943ThuleanxUntitled (POI11_rot)C++14
18 / 100
1065 ms65540 KiB
#include <bits/stdc++.h> using namespace std; const int N = 2e5+7; int n; struct BIT { vector<int> tree; vector<int> elems; BIT() { tree = vector<int>(N,0); } void add(int v) { elems.push_back(v); for (; v < n; v|=v+1) tree[v]++; } int sum(int v) { int ans = 0; for (; v >= 0; v = (v&(v+1))-1) ans += tree[v]; return ans; } int merge(BIT &other) { int ans = 0; for (int x : other.elems) ans += sum(x); for (int x : other.elems) add(x); return ans; } }; int merge(BIT &a, BIT &b) { if (a.elems.size() < b.elems.size()) swap(a,b); int y = a.elems.size() * b.elems.size(); int x = a.merge(b); return min(x, y-x); } BIT solve(int &ans) { int x; cin>>x; if (x) { BIT ds; ds.add(x-1); return ds; } else { BIT a = solve(ans), b = solve(ans); ans += merge(a,b); return a.elems.size()>b.elems.size() ? a : b; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n; int ans = 0; solve(ans); cout << ans << endl; return 0; }
#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...
#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...