Submission #466474

#	Time	Username	Problem	Language	Result	Execution time	Memory
466474		koioi.org-dennisstar	Secret (JOI14_secret)	C++17	100 / 100	539 ms	8416 KiB

secret

#include "secret.h"
#include <bits/stdc++.h>

using namespace std;

int n;
vector<vector<int>> ar;

void init(int s, int e) {
	if (s==e) return ;
	int m=(s+e)/2;
	for (int i=m; i>=s; i--) if (ar[i][m]==-1) ar[i][m]=Secret(ar[i][i], ar[i+1][m]);
	for (int i=m+1; i<=e; i++) if (ar[m+1][i]==-1) ar[m+1][i]=Secret(ar[m+1][i-1], ar[i][i]);
	init(s, m); init(m+1, e);
}

void Init(int n, int a[]) {
	::n=n;
	ar.resize(n, vector<int>(n, -1));
	for (int i=0; i<n; i++) ar[i][i]=a[i];
	init(0, n-1);
}

int Query(int l, int r) {
	int s=0, e=n-1;
	while (1) {
		int m=(s+e)/2;
		if (l<=m&&m<=r) {
			if (m==r) return ar[l][m];
			return Secret(ar[l][m], ar[m+1][r]);
		}
		if (m<l) s=m+1;
		else e=m;
	}
}

• Subtask 1: 100 / 100