Submission #1057279

#TimeUsernameProblemLanguageResultExecution timeMemory
1057279fryingducSecret (JOI14_secret)C++17
100 / 100
276 ms8300 KiB
#include "bits/stdc++.h" using namespace std; #ifndef duc_debug #include "secret.h" #endif const int maxn = 1e3 + 3; int n, a[maxn]; int pref[maxn][maxn]; void solve(int l, int r) { int mid = (l + r) / 2; pref[mid][mid] = a[mid]; pref[mid + 1][mid + 1] = a[mid + 1]; for(int i = mid + 2; i <= r; ++i) { pref[mid + 1][i] = Secret(pref[mid + 1][i - 1], a[i]); } for(int i = mid - 1; i >= l; --i) { pref[mid][i] = Secret(a[i], pref[mid][i + 1]); } if(l < mid) { solve(l, mid); } if(mid + 1 < r) { solve(mid + 1, r); } } void Init(int _n, int _a[]) { n = _n; for(int i = 0; i < n; ++i) { a[i] = _a[i]; } solve(0, n - 1); } int Query(int l, int r) { int x = 0, y = n - 1; while(x < y) { int mid = (x + y) / 2; if(l <= mid and mid < r) { return Secret(pref[mid][l], pref[mid + 1][r]); } else if(mid == r) return pref[mid][l]; else if(mid < l) x = mid + 1; else y = mid; } return pref[x][x]; }
#Verdict Execution timeMemoryGrader output
Fetching results...