# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1189185 | qrn | Secret (JOI14_secret) | C++20 | 0 ms | 0 KiB |
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
#define intt long long
#define int long long
const intt mxN = 1e3 + 31;
vector<vector<intt>> V(mxN, vector<intt>(mxN, 0ll));
vector<intt> a(mxN);
intt border;
void build(intt l, intt r) {
if(l > r) return;
intt mid = (l + r) / 2;
V[mid][mid] = a[mid];
V[mid+1][mid+1] = a[mid+1];
for(intt i = mid + 2; i <= r; i++) {
V[mid+1][i] = Secret(V[mid+1][i-1], a[i]);
}
if(mid - 1 >= 0) {
for(intt i = mid - 1; i >= l; i--) {
V[i][mid] = Secret(a[i], V[i+1][mid]);
}
}
if(l == r) return;
build(l, mid);
build(mid+1, r);
}
intt get(intt ql, intt qr) {
if(ql == qr) {
return a[ql];
}
intt l = 0, r = border;
while(l <= r) {
intt mid = (l + r) / 2;
if(ql <= mid && mid + 1 <= qr) {
return Secret(V[ql][mid], V[mid+1][qr]);
}
if(ql > mid) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return -1;
}
void Init(int N, int A[]) {
for(intt i = 0; i < N; i++) {
a[i] = A[i];
}
//1 4 7 2 5 8 3 6
border = N - 1;
build(0, border);
}
int Query(int L, int R) {
return get(L, R);
}