Submission #1276273

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276273		WH8	Secret (JOI14_secret)	C++20	100 / 100	336 ms	4580 KiB

secret

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

struct node {
	int s,e,m;
	vector<int> pre, suf;
	node *l, *r;
	node (int S, int E, int A[]){
		s=S, e=E, m=(s+e)/2;
		if(s==e){
			suf.push_back(A[s]);
			return;
		}
		l=new node(s,m,A);
		r=new node(m+1,e,A);
		suf.push_back(A[m]);
		pre.push_back(A[m+1]);
		for(int i=m-1;i>=s;i--){
			suf.push_back(Secret(A[i], suf.back()));
		}
		for(int i=m+2;i<=e;i++){
			pre.push_back(Secret(pre.back(),A[i]));
		}
	}
	int query(int S, int E){
		if(s==e)return suf[0];
		if(S > m)return r->query(S,E);
		else if(E<=m)return l->query(S,E);
		return Secret(suf[m-S], pre[E-m-1]);
	}
} *root;
	

void Init(int N, int A[]) {
	root=new node(0, N-1, A);
}

int Query(int L, int R) {
	return root->query(L,R);
}

• Subtask 1: 100 / 100