#include "secret.h"
#include <vector>
using namespace std;
template<class T> struct offlineDQ {
static const int SZ = (1 << 10);
int n;
T stor[SZ][32-__builtin_clz(SZ)], id = 1;
vector<T> a;
T comb (T a, T b) { return (a == -1 ? b : (b == 1 ? a : Secret(a, b))); } // associative operation
void fill(int l, int r, int ind) {
if (ind < 0) return;
int m = (l+r)/2;
T prod = a[m - 1];
if(l <= m - 1) stor[m - 1][ind] = prod;
for(int i = m - 2; i >= l; i--) stor[i][ind] = prod = comb(a[i],prod);
prod = a[m];
if(m < r) stor[m][ind] = prod;
for(int i = m + 1; i < r; i++) stor[i][ind] = prod = comb(prod,a[i]);
fill(l,m,ind-1); fill(m,r,ind-1);
}
void init() {
n = 1; while ((1<<n) < (int)a.size()) ++n;
// while(a.size() < (1 << n)) a.push_back(-1);
a.resize((1 << n));
fill(0,(1<<n),n-1);
}
T query(int l, int r) {
if (l == r) return a[l];
int t = 31-__builtin_clz(r^l);
return comb(stor[l][t],stor[r][t]);
}
};
offlineDQ<int> odq;
void Init(int N, int A[]) {
odq.a.resize(N);
for(int i = 0; i < N; i++) odq.a[i] = A[i];
odq.init();
}
int Query(int L, int R) {
return odq.query(L, R);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
118 ms |
2312 KB |
Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1 |
| 2 |
Correct |
118 ms |
2280 KB |
Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1 |
| 3 |
Partially correct |
123 ms |
2384 KB |
Output isn't correct - number of calls to Secret by Init = 8194, maximum number of calls to Secret by Query = 1 |
| 4 |
Partially correct |
417 ms |
4252 KB |
Output isn't correct - number of calls to Secret by Init = 8194, maximum number of calls to Secret by Query = 1 |
| 5 |
Partially correct |
420 ms |
4300 KB |
Output isn't correct - number of calls to Secret by Init = 8194, maximum number of calls to Secret by Query = 1 |
| 6 |
Partially correct |
416 ms |
4424 KB |
Output isn't correct - number of calls to Secret by Init = 8194, maximum number of calls to Secret by Query = 1 |
| 7 |
Partially correct |
422 ms |
4248 KB |
Output isn't correct - number of calls to Secret by Init = 8194, maximum number of calls to Secret by Query = 1 |
| 8 |
Partially correct |
420 ms |
4428 KB |
Output isn't correct - number of calls to Secret by Init = 8194, maximum number of calls to Secret by Query = 1 |
| 9 |
Partially correct |
422 ms |
4300 KB |
Output isn't correct - number of calls to Secret by Init = 8194, maximum number of calls to Secret by Query = 1 |
| 10 |
Partially correct |
425 ms |
4244 KB |
Output isn't correct - number of calls to Secret by Init = 8194, maximum number of calls to Secret by Query = 1 |
