#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;
map<pi,int> mp;
vi a;
int n;
set<pi> st;
void solve(int l,int r){
if(l==r)return;
if(l+1==r){
mp[{l,r}]=Secret(a[l],a[r]);
return;
}
int m=(l+r)/2;
solve(0,m);
solve(m+1,r);
int c=a[m];
for(int i=m-1;i>=l;i--){
if(st.count({i,m})==0){
mp[{i,m}]=Secret(a[i],c);
c=mp[{i,m}];
st.insert({i,m});
}
else c=mp[{i,m}];
}
c=a[m+1];
REP(i,m+2,r+1){
if(st.count({m+1,i})==0){
mp[{m+1,i}]=Secret(c,a[i]);
c=mp[{m+1,i}];
st.insert({m+1,i});
}
else c=mp[{m+1,i}];
}
}
void Init(int N, int A[]) {
n=N;
a.resize(n);
REP(i,0,n){
a[i]=A[i];
mp[{i,i}]=A[i];
st.insert({i,i});
}
solve(0,n-1);
}
int Query(int L, int R) {
auto it=st.lower_bound({L+1,0});
it=prev(it);
int m=it->S;
return Secret(mp[{L,m}],mp[{m+1,R}]);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |