Submission #1200921

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200921		PlayVoltz	Secret (JOI14_secret)	C++20	100 / 100	344 ms	4516 KiB

secret

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

int n, mx=0;
vector<int> vect;
vector<vector<int> > ans;

void dnc(int l, int r, int layer){
	if (l==r)return;
	int m=(l+r)/2;
	ans[m][layer]=vect[m];
	ans[m+1][layer]=vect[m+1];
	for (int i=m-1; i>=l; --i)ans[i][layer]=Secret(vect[i], ans[i+1][layer]);
	for (int i=m+2; i<=r; ++i)ans[i][layer]=Secret(ans[i-1][layer], vect[i]);
	dnc(l, m, layer+1);
	dnc(m+1, r, layer+1);
}

void Init(int N, int a[]){
	n=N;
	vect.resize(n);
	for (int i=0; i<n; ++i)vect[i]=a[i];
	ans.resize(n, vector<int>(20));
	dnc(0, n-1, 0);
}

int Query(int l, int r) {
	if (l==r)return vect[l];
	int cl=0, cr=n-1, c=0;
	while (1){
		int m=(cl+cr)/2;
		if (l<=m&&r>m)return Secret(ans[l][c], ans[r][c]);
		else if (r<=m)cr=m;
		else cl=m+1;
		++c;
	}
	return Secret(ans[l][c], ans[r][c]);
}

• Subtask 1: 100 / 100