# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
624468 | 2022-08-08T10:05:20 Z | erto | Secret (JOI14_secret) | C++17 | 0 ms | 0 KB |
//#include "secret.h" #include <bits/stdc++.h> typedef long long int ll; #define INF 1000000007 #define INF2 998244353 //#define N (ll)(2e5+ 5) using namespace std; int n; int ans[1005][1005]; void calc(int lb, int rb, int A[]){ int mid = (lb + rb) / 2; ans[mid][mid] = A[mid - 1]; if(lb == rb)return; for(int i=mid - 1; i>=lb; i--){ ans[mid][i] = Secret(A[i - 1], ans[mid][i + 1]); } ans[mid + 1][mid + 1] = A[mid]; for(int i=mid + 2; i<=rb; i++){ ans[mid + 1][i] = Secret(ans[mid + 1][i - 1], A[i - 1]); } calc(lb, mid, A); calc(mid + 1, rb, A); } void Init(int N, int A[]){ n = N; calc(1, n, A); } int Query(int L, int R){ L++; R++; int a = 1, b = n; if(L == R)return ans[L - 1][L - 1]; else{ while(a < b){ int mid = (a + b) / 2; if(L <= mid && mid < R){ return Secret(ans[mid][L], ans[mid][R]); } else if(mid == R){ return ans[mid][L]; } else if(mid < L){ a = mid + 1; } else{ b = mid; } } } }