#include "secret.h"
#include <bits/stdc++.h>
typedef std::pair<int,int> pii;
#define f first
#define s second
const int maxn = 1030;
int v[maxn], n;
class Seg{
public:
void build(int node, int l, int r){
if(l == r){
pref[node].push_back(v[l]);
return;
}
int mid = (l + r) >> 1;
int val;
for(int i=mid; i>=l; i--){
if(i == mid) suf[node].push_back(val = v[i]);
else suf[node].push_back(val = Secret(v[i], val));
}
for(int i=mid+1; i<=r; i++){
if(i == mid+1) pref[node].push_back(val = v[i]);
else pref[node].push_back(val = Secret(val, v[i]));
}
build(2*node, l, mid), build(2*node+1, mid+1, r);
}
int query(int node, int tl, int tr, int l, int r){
int mid = (tl + tr) >> 1;
if(tl == tr) return pref[node].front();
if(l <= mid and mid+1 <= r){
return Secret(suf[node][mid - l], pref[node][r - mid - 1]);
}
else if(l >= mid+1) return query(2*node+1, mid+1, tr, l, r);
else return query(2*node, tl, mid, l, r);
}
private:
std::vector<int> pref[2*maxn], suf[2*maxn];
}seg;
void Init(int N, int A[]) {
n = N;
for(int i=1; i<=N; i++) v[i] = A[i-1];
seg.build(1, 1, n);
}
int Query(int L, int R) {
L++, R++;
return seg.query(1, 1, n, L, R);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
156 ms |
2540 KB |
Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1 |
| 2 |
Correct |
144 ms |
2796 KB |
Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1 |
| 3 |
Correct |
144 ms |
2540 KB |
Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1 |
| 4 |
Correct |
508 ms |
4588 KB |
Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1 |
| 5 |
Correct |
518 ms |
4652 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |
| 6 |
Correct |
540 ms |
4612 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |
| 7 |
Correct |
509 ms |
4588 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |
| 8 |
Correct |
507 ms |
4588 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |
| 9 |
Correct |
513 ms |
4716 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |
| 10 |
Correct |
512 ms |
4588 KB |
Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1 |
