Submission #238238

#TimeUsernameProblemLanguageResultExecution timeMemory
238238MrRobot_28Dojave (COCI17_dojave)C++17
42 / 140
1201 ms262148 KiB
#include<bits/stdc++.h> using namespace std; #define int long long vector <vector <int> > tree, treecnt, upd; void push(int ind, int v, int l, int r) { tree[ind][v * 2] += upd[ind][v]; tree[ind][v * 2 + 1] += upd[ind][v]; upd[ind][v * 2] += upd[ind][v]; upd[ind][v * 2 + 1] += upd[ind][v]; upd[ind][v] = 0; } void update(int ind, int v, int l, int r, int al, int ar, int val) { if(l >= al && r <= ar) { tree[ind][v] += val; upd[ind][v] += val; } else if(l <= ar && r >= al) { push(ind, v, l, r); update(ind, v * 2, l, (r + l) / 2, al, ar, val); update(ind, v * 2 + 1, (r + l) / 2 + 1, r, al, ar, val); if(tree[ind][v * 2] == tree[ind][v * 2 + 1]) { tree[ind][v] = tree[ind][v * 2]; treecnt[ind][v] = treecnt[ind][v * 2] + treecnt[ind][v * 2 + 1]; } else if(tree[ind][v * 2] < tree[ind][v * 2 + 1]) { tree[ind][v] = tree[ind][v * 2]; treecnt[ind][v] = treecnt[ind][v * 2]; } else { tree[ind][v] = tree[ind][v * 2 + 1]; treecnt[ind][v] = treecnt[ind][v * 2 + 1]; } } } pair <int, int> ans(int ind, int v, int l, int r, int al, int ar){ if(l >= al && r <= ar) { return {tree[ind][v], treecnt[ind][v]}; } else if(l <= ar && r >= al) { push(ind, v, l ,r); pair <int, int> v1 = ans(ind, v * 2, l, (r + l) / 2, al, ar); pair <int, int> v2 = ans(ind, v * 2 + 1, (r + l) / 2 + 1, r, al, ar); if(v1.first == v2.first) { return {v1.first, v1.second + v2.second}; } else if(v1.first < v2.first){ return v1; } else { return v2; } } else { return {1e9, 0}; } } void build(int ind, int v, int l, int r) { if(l == r){ treecnt[ind][v] = 1; if(l % 4 == ind){ tree[ind][v] = 0; } else { tree[ind][v] = 1e9; } return; } build(ind, v * 2, l, (r + l) / 2); build(ind, v * 2 + 1, (r + l) / 2 + 1, r); tree[ind][v] = min(tree[ind][v * 2], tree[ind][v * 2 + 1]); if(tree[ind][v * 2] == tree[ind][v * 2 + 1]) { tree[ind][v] = tree[ind][v * 2]; treecnt[ind][v] = treecnt[ind][v * 2] + treecnt[ind][v * 2 + 1]; } else if(tree[ind][v * 2] < tree[ind][v * 2 + 1]) { tree[ind][v] = tree[ind][v * 2]; treecnt[ind][v] = treecnt[ind][v * 2]; } else { tree[ind][v] = tree[ind][v * 2 + 1]; treecnt[ind][v] = treecnt[ind][v * 2 + 1]; } } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; int m = pow(2, n); vector <int> A(m); vector <int> ind(m, -1); int w1 = 0, w2 = 0; for(int i = 0; i < m; i++) { cin >> A[i]; ind[A[i]] = i; w1 = w1 ^ A[i]; w2 = w2 ^ A[i]; } tree.resize(4, vector <int> (4 * m, 0)); treecnt.resize(4, vector <int> (4 * m, 0)); upd.resize(4, vector <int> (4 * m, 0)); int sum = 0; for(int i= 0; i < 4; i++) { build(i, 1, 0, m - 1); } w1 ^= A[0]; w2 ^= A[m - 1]; if(w1 == m - 1) { sum++; } if(w2 == m - 1) { sum++; } for(int i = m - 1; i >= 0; i--) { if(ind[m - 1 - A[i]] > i) { for(int j = 0; j < 4; j++) { update(j, 1, 0, m - 1, ind[m - 1 - A[i]], m - 1, -2); } } for(int j = 0; j < 4; j++) { update(j, 1, 0, m - 1, i, m - 1, 1); } pair <int, int> v = ans((i + 3) % 4, 1, 0, m - 1, i, m - 1); if(v.first == 0) { sum += v.second; } } sum = (m + 1) * m / 2 - sum; cout << sum; 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...