#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
map<pair<int,int>, int> mp;
template<class T, int SZ> struct RangeQuery {
int n;
T stor[SZ][31-__builtin_clz(SZ)], id = 1;
vector<T> a;
T comb(T a, T b) {
if (mp.count({a, b})) return mp[{a,b}];
if (mp.count({b, a})) return mp[{b,a}];
return mp[{a,b}] = Secret(a, b);
}
void fill(int l, int r, int ind) {
if (ind < 0) return;
int m = (l + r) >> 1;
T pre = stor[m-1][ind] = a[m-1];
for (int i = m-2; i >= l; i--) stor[i][ind] = pre = comb(a[i], pre);
pre = stor[m][ind] = a[m];
for (int i = m+1; i < r; i++) stor[i][ind] = pre = comb(pre, a[i]);
fill(l, m, ind-1); fill(m, r, ind-1);
}
void init() {
n = 1; while ((1<<n) < a.size()) n++;
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]);
}
};
RangeQuery<int, (1<<10)> rq;
void Init(int N, int A[]) {
rq.a.resize(N);
for (int i = 0; i < N; i++) {
rq.a[i] = A[i];
}
rq.init();
}
int Query(int L, int R) {
return rq.query(L, R);
}
Compilation message
secret.cpp: In instantiation of 'void RangeQuery<T, SZ>::init() [with T = int; int SZ = 1024]':
secret.cpp:41:10: required from here
secret.cpp:25:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | n = 1; while ((1<<n) < a.size()) n++;
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
148 ms |
3164 KB |
Output is correct - number of calls to Secret by Init = 3332, maximum number of calls to Secret by Query = 1 |
| 2 |
Correct |
147 ms |
3184 KB |
Output is correct - number of calls to Secret by Init = 3332, maximum number of calls to Secret by Query = 1 |
| 3 |
Correct |
149 ms |
3268 KB |
Output is correct - number of calls to Secret by Init = 3847, maximum number of calls to Secret by Query = 1 |
| 4 |
Correct |
509 ms |
5372 KB |
Output is correct - number of calls to Secret by Init = 7498, maximum number of calls to Secret by Query = 1 |
| 5 |
Correct |
514 ms |
5444 KB |
Output is correct - number of calls to Secret by Init = 7511, maximum number of calls to Secret by Query = 1 |
| 6 |
Correct |
505 ms |
5164 KB |
Output is correct - number of calls to Secret by Init = 7512, maximum number of calls to Secret by Query = 1 |
| 7 |
Correct |
520 ms |
5324 KB |
Output is correct - number of calls to Secret by Init = 7509, maximum number of calls to Secret by Query = 1 |
| 8 |
Correct |
513 ms |
5316 KB |
Output is correct - number of calls to Secret by Init = 7511, maximum number of calls to Secret by Query = 1 |
| 9 |
Correct |
519 ms |
5308 KB |
Output is correct - number of calls to Secret by Init = 7511, maximum number of calls to Secret by Query = 1 |
| 10 |
Correct |
516 ms |
5344 KB |
Output is correct - number of calls to Secret by Init = 7511, maximum number of calls to Secret by Query = 1 |
