#include "secret.h"
#include <vector>
using namespace std;
template<class T> struct onlineDQ {
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) { if(a == -1) return b; if(b == -1) return b; return Secret(a, b); } // associative operation
void fill(int l, int r, int ind) {
if(l == r) {
stor[l][ind] = a[l];
return;
}
if(ind < 0) return;
int m = (l+r)/2;
stor[m][ind] = a[m];
for(int i = m - 1; i >= l; i--) stor[i][ind] = comb(a[i], stor[i + 1][ind]);
stor[m + 1][ind] = a[m + 1];
for(int i = m + 2; i < r; i++) stor[i][ind] = comb(stor[i - 1][ind] ,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);
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]);
}
};
onlineDQ<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);
}
Compilation message
secret.cpp: In member function 'void onlineDQ<T>::fill(int, int, int)':
secret.cpp:16:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
16 | if(ind < 0) return;
| ^~
secret.cpp:17:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
17 | int m = (l+r)/2;
| ^~~
secret.cpp: In instantiation of 'void onlineDQ<T>::init() [with T = int]':
secret.cpp:41:12: required from here
secret.cpp:26:20: warning: comparison of integer expressions of different signedness: 'std::vector<int, std::allocator<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
26 | while(a.size() < (1 << n)) a.push_back(-1);
| ~~~~~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
110 ms |
2380 KB |
Wrong Answer: Query(493, 496) - expected : 990344084, actual : 692145173. |
| 2 |
Incorrect |
110 ms |
2276 KB |
Wrong Answer: Query(236, 238) - expected : 173116186, actual : 800141843. |
| 3 |
Incorrect |
115 ms |
2296 KB |
Wrong Answer: Query(130, 131) - expected : 127065177, actual : 260103225. |
| 4 |
Incorrect |
421 ms |
4312 KB |
Wrong Answer: Query(216, 220) - expected : 518824820, actual : 467952034. |
| 5 |
Incorrect |
426 ms |
4304 KB |
Wrong Answer: Query(584, 592) - expected : 111053842, actual : 895372370. |
| 6 |
Incorrect |
416 ms |
4420 KB |
Wrong Answer: Query(200, 208) - expected : 277813445, actual : 966582165. |
| 7 |
Partially correct |
425 ms |
4316 KB |
Output isn't correct - number of calls to Secret by Init = 8486, maximum number of calls to Secret by Query = 1 |
| 8 |
Partially correct |
426 ms |
4372 KB |
Output isn't correct - number of calls to Secret by Init = 8486, 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 = 8486, maximum number of calls to Secret by Query = 1 |
| 10 |
Partially correct |
433 ms |
4388 KB |
Output isn't correct - number of calls to Secret by Init = 8486, maximum number of calls to Secret by Query = 1 |
