Submission #1153672

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153672		nikolashami	Secret (JOI14_secret)	C++20	0 / 100	20089 ms	4688 KiB

secret

#include"secret.h"
#include<bits/stdc++.h>
using namespace std;
using ll=long long;

const ll NN=1e3+2;
ll n,a[NN];

vector<ll>suf[4*NN],pref[4*NN];

void f(ll l,ll r,ll i){
	if(l==r){pref[i]={a[l]};return;}
	ll m=(l+r)/2;
	suf[i].resize(m-l);
	pref[i].resize(r-m-1);
	ll cur=a[m],point=0;
	for(int j=m-1;j>=l;--j){
		ll sc=Secret(a[j],cur);
		suf[i][point++]=sc;
		cur=sc;
	}
	cur=a[m+1],point=0;
	for(int j=m+2;j<=r;++j){
		ll sc=Secret(cur,a[j]);
		pref[i][point++]=sc;
		cur=sc;
	}
	f(l,m,i*2);
	f(m+1,r,i*2+1);
}

void Init(int N,int A[]){
	n=N;
	for(int i=1;i<=n;++i)a[i]=A[i-1];
	f(1,n,1);
}

array<ll,2>fnd(ll l,ll r){
	ll i=1,L=1,R=n;
	while(1){
		ll md=(L+R)/2;
		if(md>=l&&md+1<=r)
			return{i,md};
		if(md>=r){
			R=md;
			i<<=1;
		}else{
			L=md+1;
			i<<=1;++i;
		}
	}
	return{-1,-1};
}

int Query(int l,int r){
	++l,++r;
	auto[i,m]=fnd(l,r);
	assert(i!=-1);
	ll lft=-1;
	if(l==m)lft=a[l];
	else lft=suf[i][m-l-1];
	ll rgt=-1;
	if(r==1+m)rgt=a[r];
	else rgt=pref[i][r-m-2];
	assert(lft!=-1&&rgt!=-1);
	return Secret(lft,rgt);
}

• Subtask 1: 0 / 100