#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define a first
#define b second
#define pb push_back
#include "secret.h"
/*int Secret(int x,int y){
// cout<<x<<" "<<2*(y/2)<<endl;
return x+2*(y/2);
}*/
//int block=
int n;
int it[1001];
vector<int> tree[1000001][2];
void pre(int no,int l,int r){
if(l>r){
return;
}
if(l==r){
tree[no][0].pb(it[l]);
}
else{
int mid=(l+r)/2;
int co=it[mid];
tree[no][0].pb(co);
for(int i=mid-1;i>=l;i--){
co=Secret(it[i],co);
tree[no][0].pb(co);
// cout<<mid<<","<<i<<","<<co<<endl;
}
co=it[mid+1];
tree[no][1].pb(co);
for(int i=mid+2;i<=r;i++){
co=Secret(co,it[i]);
tree[no][1].pb(co);
// cout<<mid<<":"<<i<<" "<<co<<endl;
}
pre(no*2+1,l,mid-1);
pre(no*2+2,mid+1,r);
}
}
void Init(int nn,int aa[]){
n=nn;
for(int i=0;i<n;i++){
it[i]=aa[i];
}
pre(0,0,n-1);
}
int q(int no,int l,int r,int aa,int bb){
if(l>r){
return -1;
}
if(l==r){
return it[l];
}
else{
int mid=(l+r)/2;
if(aa<=mid and bb>mid){
// cout<<l<<','<<r<<endl;
// cout<<tree[no][0][mid-aa]<<","<<tree[no][1][bb-mid-1]<<endl;
return Secret(tree[no][0][mid-aa],tree[no][1][bb-mid-1]);
}
else if(bb==mid){
return tree[no][0][mid-aa];
}
if(bb<mid){
return q(no*2+1,l,mid-1,aa,bb);
}
else{
return q(no*2+2,mid+1,r,aa,bb);
}
}
}
int Query(int l,int r){
return q(0,0,n-1,l,r);
}
/*int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin>>n;
int bb[n];
for(int i=0;i<n;i++){
cin>>bb[i];
}
Init(n,bb);
int qo;
cin>>qo;
int l,r;
while(qo--){
cin>>l>>r;
cout<<Query(l,r)<<endl;;
}
return 0;
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
179 ms |
49400 KB |
Output is correct - number of calls to Secret by Init = 3331, maximum number of calls to Secret by Query = 1 |
| 2 |
Correct |
178 ms |
49400 KB |
Output is correct - number of calls to Secret by Init = 3339, maximum number of calls to Secret by Query = 1 |
| 3 |
Correct |
177 ms |
49400 KB |
Output is correct - number of calls to Secret by Init = 3347, maximum number of calls to Secret by Query = 1 |
| 4 |
Correct |
547 ms |
51448 KB |
Output is correct - number of calls to Secret by Init = 7467, maximum number of calls to Secret by Query = 1 |
| 5 |
Correct |
551 ms |
51376 KB |
Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1 |
| 6 |
Correct |
545 ms |
51576 KB |
Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1 |
| 7 |
Correct |
548 ms |
51320 KB |
Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1 |
| 8 |
Correct |
551 ms |
51424 KB |
Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1 |
| 9 |
Correct |
563 ms |
51448 KB |
Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1 |
| 10 |
Correct |
552 ms |
51448 KB |
Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1 |
