#include "secret.h"
#include <bits/stdc++.h>
#define pf first
#define sf second
using namespace std;
const int N=1<<10;
vector<vector<pair<int,int>>>segt(N*2);
void upd(int i,int x){
i+=N;
segt[i]=vector<pair<int,int>>(1,{x,x});
for(i/=2;i;i/=2){
auto v1=segt[i*2];
auto v2=segt[i*2+1];
if(v1.empty()||v2.empty()){
break;
}
int h=v1.size();
segt[i].resize(h*2);
for(int j=0;j<h*2;j++){
if(j<h){
segt[i][j].pf=v1[j].pf;
}else{
segt[i][j].pf=Secret(v1.back().pf,v2[j-h].pf);
}
}
for(int j=h*2-1;j>=0;j--){
if(j>=h){
segt[i][j].sf=v2[j-h].sf;
}else{
segt[i][j].sf=Secret(v1[j].sf,v2[0].sf);
}
}
}
}
void Init(int n, int a[]) {
for(int i=0;i<n;i++){
upd(i,a[i]);
}
}
int Query(int l, int r) {
int lo=l,ro=r;
l+=N;
r+=N;
if(l==r){
return segt[l][0].pf;
}
while(l+1<r){
l/=2;r/=2;
}
int h=segt[l].size();
lo%=h;
ro%=h;
int res=Secret(segt[l][lo].sf,segt[r][ro].pf);
//cout<<l<<" "<<r<<" "<<lo<<" "<<ro<<" "<<h<<" "<<segt[l][lo].sf<<" "<<segt[r][ro].pf<<endl;
return res;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |