# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1110541 | vladilius | Secret (JOI14_secret) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
vector<vector<int>> x;
vector<int> a;
int n, lg;
void build(int d, int l, int r){
if (abs(l - r) <= 1) return;
int m = (l + r) / 2;
x[d][m] = a[m];
for (int i = m - 1; i >= l; i--){
x[d][i] = Secret(x[d][i + 1], a[i]);
}
x[d][m + 1] = a[m + 1];
for (int i = m + 2; i <= r; i++){
x[d][i] = Secret(x[d][i - 1], a[i]);
}
build(d + 1, l, m);
build(d + 1, m + 1, r);
}
void Init(int ns, vector<int> A){
n = ns;
a.resize(n + 1);
for (int i = 1; i <= n; i++){
a[i] = A[i - 1];
}
lg = log2(n);
x.resize(lg + 1);
for (int i = 0; i <= lg; i++){
x[i].resize(n + 1);
}
build(0, 1, n);
}
int get(int d, int tl, int tr, int& l, int& r){
int tm = (tl + tr) / 2;
if (l <= tm && tm < r){
return Secret(x[d][l], x[d][r]);
}
return (r <= tm) ? get(d + 1, tl, tm, l, r) : get(d + 1, tm + 1, tr, l, r);
}
int Query(int l, int r){
l++; r++;
if ((l + 1) == r) return Secret(a[l], a[r]);
return get(0, 1, n, l, r);
}