# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1086193 | f0rizen | Secret (JOI14_secret) | C++17 | 314 ms | 4496 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 "secret.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll infll = 1e18;
template<typename T, class F = function<T(T, T)>>
struct DST {
static const int lg = 10;
vector<int> a;
array<vector<int>, lg> st;
vector<int> mask;
F func;
DST() {}
DST(const vector<int> &_a, const F &f) : a(_a), func(f) {
int n = a.size();
for (int i = 0; i < lg; ++i) {
st[i].resize(n);
}
mask.resize(n);
build(0, n - 1, 0);
}
void build(int l, int r, int k) {
if (l == r) {
return;
}
int mid = (l + r) / 2;
st[k][mid] = a[mid];
for (int i = mid - 1; i >= l; --i) {
st[k][i] = func(a[i], st[k][i + 1]);
}
st[k][mid + 1] = a[mid + 1];
for (int i = mid + 2; i <= r; ++i) {
st[k][i] = func(st[k][i - 1], a[i]);
}
for (int i = mid + 1; i <= r; ++i) {
mask[i] ^= (1 << k);
}
build(l, mid, k + 1);
build(mid + 1, r, k + 1);
}
// [l, r]
int get(int l, int r) {
if (l == r) {
return a[l];
}
int k = __builtin_ctz(mask[l] ^ mask[r]);
return func(st[k][l], st[k][r]);
}
};
DST<int> dst;
void Init(int N, int A[]) {
vector<int> a(N);
for (int i = 0; i < N; ++i) {
a[i] = A[i];
}
dst = DST<int>(a, [](int a, int b) {
return Secret(a, b);
});
}
int Query(int L, int R) {
return dst.get(L, R);
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |