# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
568265 | 2022-05-25T04:31:34 Z | gg123_pe | Secret (JOI14_secret) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> ii; #define f(i,a,b) for(int i = a; i < b; i++) #define fa(i,a,b) for(int i = a; i >= b; i--) #define ff first #define ss second const int N = 1005; const ll inf = 1e17 + 100; int n, a[N], L[N][N], R[N][N]; void go(int l, int r){ if(l == r){ L[l][l] = R[l][l] = a[l]; return ; } int m = (l+r)>>1; go(l, m), go(m+1, r); L[m][m] = a[m]; fa(i,m-1,l) L[m][i] = Secret(a[i], L[m][i+1]); R[m+1][m+1] = a[m+1]; f(i,m+2,r+1) R[m+1][i] = Secret(R[m+1][i-1], a[i]); } void Init(int ni, int x[]){ n = ni; f(i,0,n) a[i] = x[i]; go(0, n-1); } int Query(int x, int y){ int l = 0, r = n-1; while(1){ int m = (l+r)>>1; if(y == m) return L[x][y]; if(x == m+1) return R[x][y]; if(x <= m and m+1 <= y) return Secret(L[x][m], R[m+1][y]); if(y < m) r = m; else l = m+1; } return -1; }