#include "secret.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> centers;
vector<int> start, finish;
int val[2002][2002];
int a[2002];
int num=0;
//int Secret(int l,int r){return 0;}
void DC(int L,int R) {
if (L>R) return;
else {
int mid = (L+R)/2;
centers.push_back(mid);
start.push_back(L);
finish.push_back(R);
val[mid][mid]=a[mid];
for (int i=mid-1;i>=L;i--) val[i][mid] = Secret(a[i], val[i+1][mid]);
val[mid+1][mid+1]=a[mid+1];
for (int i=mid+2;i<=R;i++) val[mid+1][i] = Secret(val[mid+1][i-1], a[i]);
DC(L, mid-1);
DC(mid+1,R);
}
}
void Init(int N, int A[]) {
for (int i=0;i<N;i++) a[i] = A[i];
DC(0, N-1);
}
int Query(int L, int R) {
for (int i=0;i<centers.size();i++) {
if (start[i]<=L && finish[i]>=R && centers[i]<=R && centers[i]>=L) {
if (L==centers[i]+1 || R==centers[i]) return val[L][R];
return Secret(val[L][centers[i]], val[centers[i]+1][R]);
}
}
}
Compilation message
secret.cpp: In function 'int Query(int, int)':
secret.cpp:32:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for (int i=0;i<centers.size();i++) {
| ~^~~~~~~~~~~~~~~
secret.cpp:38:1: warning: control reaches end of non-void function [-Wreturn-type]
38 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
147 ms |
4600 KB |
Output is correct - number of calls to Secret by Init = 3331, maximum number of calls to Secret by Query = 1 |
| 2 |
Correct |
146 ms |
4740 KB |
Output is correct - number of calls to Secret by Init = 3339, maximum number of calls to Secret by Query = 1 |
| 3 |
Correct |
149 ms |
4600 KB |
Output is correct - number of calls to Secret by Init = 3347, maximum number of calls to Secret by Query = 1 |
| 4 |
Correct |
517 ms |
9080 KB |
Output is correct - number of calls to Secret by Init = 7467, maximum number of calls to Secret by Query = 1 |
| 5 |
Correct |
513 ms |
8952 KB |
Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1 |
| 6 |
Correct |
509 ms |
9080 KB |
Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1 |
| 7 |
Correct |
506 ms |
9060 KB |
Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1 |
| 8 |
Correct |
513 ms |
9080 KB |
Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1 |
| 9 |
Correct |
516 ms |
8952 KB |
Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1 |
| 10 |
Correct |
512 ms |
9192 KB |
Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1 |
