#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
vector<pair<int, pair<int, int>>> vc;
int b[1001];
int vals[1001][1001];
int m;
void solve(int l, int r, int lvl){
if(l+1>=r)return;
int mid=l+r>>1;
vc.push_back({mid, {lvl, 0}});
vc.push_back({mid+1, {lvl, 1}});
vals[mid][mid]=b[mid];
vals[mid+1][mid+1]=b[mid+1];
for(int i=mid-1; i>=0; i--){
vals[mid][i]=Secret(b[i], vals[mid][i+1]);
}
for(int i=mid+2; i<m; i++){
vals[mid+1][i]=Secret(vals[mid+1][i-1], b[i]);
}
solve(l, mid-1, lvl+1);
solve(mid+2, r, lvl+1);
}
void Init(int n, int a[]) {
m=n;
for(int i=0; i<n; i++)b[i]=a[i];
solve(0, n-1, 1);
sort(vc.begin(), vc.end());
}
int Query(int l, int r) {
if(l==r)return b[l];
if(l==r-1)return Secret(b[l], b[l+1]);
int mn=1e9;
int p[2]={-1, -1};
for(auto e : vc){
if(e.F>=l && e.F<=r){
if(e.S.F<mn){
p[0]=p[1]=-1;
mn=e.S.F;
p[e.S.S]=e.F;
}
else if(e.S.F==mn){
p[e.S.S]=e.F;
}
}
}
if(p[0]==-1)return vals[p[1]][r];
if(p[1]==-1)return vals[p[0]][l];
else{
return Secret(vals[p[0]][l], vals[p[1]][r]);
}
}
Compilation message
secret.cpp: In function 'void solve(int, int, int)':
secret.cpp:15:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
15 | int mid=l+r>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
149 ms |
6736 KB |
Output isn't correct - number of calls to Secret by Init = 65152, maximum number of calls to Secret by Query = 1 |
| 2 |
Partially correct |
157 ms |
6820 KB |
Output isn't correct - number of calls to Secret by Init = 65790, maximum number of calls to Secret by Query = 1 |
| 3 |
Partially correct |
147 ms |
6740 KB |
Output isn't correct - number of calls to Secret by Init = 66430, maximum number of calls to Secret by Query = 1 |
| 4 |
Partially correct |
531 ms |
7856 KB |
Output isn't correct - number of calls to Secret by Init = 254235, maximum number of calls to Secret by Query = 1 |
| 5 |
Partially correct |
537 ms |
7832 KB |
Output isn't correct - number of calls to Secret by Init = 254490, maximum number of calls to Secret by Query = 1 |
| 6 |
Partially correct |
529 ms |
8332 KB |
Output isn't correct - number of calls to Secret by Init = 254490, maximum number of calls to Secret by Query = 1 |
| 7 |
Partially correct |
536 ms |
7980 KB |
Output isn't correct - number of calls to Secret by Init = 254490, maximum number of calls to Secret by Query = 1 |
| 8 |
Partially correct |
540 ms |
7888 KB |
Output isn't correct - number of calls to Secret by Init = 254490, maximum number of calls to Secret by Query = 1 |
| 9 |
Partially correct |
534 ms |
8020 KB |
Output isn't correct - number of calls to Secret by Init = 254490, maximum number of calls to Secret by Query = 1 |
| 10 |
Partially correct |
541 ms |
8052 KB |
Output isn't correct - number of calls to Secret by Init = 254490, maximum number of calls to Secret by Query = 1 |
