#include "secret.h"
#include <map>
using namespace std;
int spt[15][1005];
int a[1005];
map<pair<int,int>, int> asked;
int ask(int x, int y){
pair<int, int> u = make_pair(x, y);
if (asked.find(u) != asked.end()) return asked[u];
return asked[u] = Secret(x, y);
}
void rec(int l, int r, int d = 0){
if (l == r){
spt[d][l] = a[l];
return;
}
int md = (l + r) >> 1;
rec(l, md, d + 1); rec(md + 1, r, d + 1);
int prv = a[md];
spt[d][md] = a[md];
for (int i = md - 1; i >= l; --i){
spt[d][i] = ask(a[i], prv);
prv = spt[d][i];
}
prv = a[md + 1];
spt[d][md + 1] = a[md + 1];
for (int i = md + 2; i <= r; i++){
spt[d][i] = ask(prv, a[i]);
prv = spt[d][i];
}
}
int n;
void Init(int N, int A[]){
n = N;
for (int i = 0; i < N; i++) a[i] = A[i];
rec(0, N - 1);
}
int ans(int i, int j, int l, int r, int d = 0){
if (l == r) return spt[d][l];
int md = (l + r) >> 1;
if (j <= md) return ans(i, j, l, md, d + 1);
else if (i >= md + 1) return ans(i, j, md+1, r, d+1);
else {
return ask(spt[d][i], spt[d][j]);
}
}
int Query(int L, int R){
return ans(L, R, 0, n - 1);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
176 ms |
3320 KB |
Output is correct - number of calls to Secret by Init = 3324, maximum number of calls to Secret by Query = 1 |
| 2 |
Correct |
177 ms |
3252 KB |
Output is correct - number of calls to Secret by Init = 3332, maximum number of calls to Secret by Query = 1 |
| 3 |
Correct |
176 ms |
3192 KB |
Output is correct - number of calls to Secret by Init = 3341, maximum number of calls to Secret by Query = 1 |
| 4 |
Correct |
603 ms |
5460 KB |
Output is correct - number of calls to Secret by Init = 7483, maximum number of calls to Secret by Query = 1 |
| 5 |
Correct |
607 ms |
5468 KB |
Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1 |
| 6 |
Correct |
607 ms |
5440 KB |
Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1 |
| 7 |
Correct |
610 ms |
5552 KB |
Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1 |
| 8 |
Correct |
606 ms |
5748 KB |
Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1 |
| 9 |
Correct |
606 ms |
5564 KB |
Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1 |
| 10 |
Correct |
604 ms |
5448 KB |
Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1 |
