Submission #525916

#	Time	Username	Problem	Language	Result	Execution time	Memory
525916		Nihal_9936	Secret (JOI14_secret)	C++14	100 / 100	455 ms	8212 KiB

secret

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

int dp[1001][1001];
int n;

void solve(int f, int l, int A[]){
	int mid = (f + l) / 2;
	dp[mid][mid] = A[mid];
	dp[mid + 1][mid + 1] = A[mid + 1];

	for(int i = mid - 1; i >= f; i--){
		dp[mid][i] = Secret(A[i], dp[mid][i + 1]);
	}

	for(int i = mid + 2; i <= l; i++){
		dp[mid + 1][i] = Secret(dp[mid + 1][i - 1], A[i]);
	}

	if(f < mid) solve(f, mid, A);
	if(mid + 1 < l) solve(mid + 1, l, A); 
}


void Init(int N, int A[]) {
	// for(int i = 0; i < 1001; i++){
	// 	for(int j = 0; j < 1001; j++){
	// 		dp[i][j] = -1;
	// 	}
	// }
	n = N;
	solve(0, n - 1, A);
}

int Query(int l, int r){
	int f = 0, ls = n - 1;
	while(true){
		int mid = (f + ls) / 2;
		if(l <= mid and mid < r){
			return Secret(dp[mid][l], dp[mid + 1][r]);
		}
		if(mid == r) return dp[mid][l];

		if(r <= mid){
			ls = mid;
		}else{
			f = mid + 1;
		}
	}
}

• Subtask 1: 100 / 100