Submission #25245

#	Time	Username	Problem	Language	Result	Execution time	Memory
25245		zigui	Secret (JOI14_secret)	C++14	100 / 100	649 ms	5348 KiB

secret

#include "secret.h"
#include<vector>

using namespace std;

const int MX = 1005;

vector<int> L[MX], R[MX];
int B[MX], N;

void get_LR(int s, int e, int A[]){
	if( s == e ) return;
	int m = (s+e) / 2;
	L[m].push_back(A[m]);
	for(int i = m-1; i >= s; i--){
		L[m].push_back(Secret(A[i], L[m].back()));
	}
	R[m].push_back(A[m+1]);
	for(int i = m+2; i <= e; i++){
		R[m].push_back(Secret(R[m].back(), A[i]));
	}
	get_LR(s, m, A);
	get_LR(m+1, e, A);
}

void Init(int N, int A[]) {
	::N = N;
	get_LR(0, N-1, A);
	for(int i = 0; i < N; i++) B[i] = A[i];
}

int get_answer(int s, int e, int l, int r){
	int m = (s+e) / 2;
	if( l <= m && m+1 <= r ){
		return Secret(L[m][m-l], R[m][r-m-1]);
	}
	else if( m < l ) return get_answer(m+1, e, l, r);
	else return get_answer(s, m, l, r);
}

int Query(int L, int R) {
	if( L == R ) return B[L];
	return get_answer(0, N-1, L, R);
}

• Subtask 1: 100 / 100