Submission #321635

#	Time	Username	Problem	Language	Result	Execution time	Memory
321635		Kenzo_1114	Secret (JOI14_secret)	C++17	0 / 100	500 ms	8428 KiB

secret

#include<bits/stdc++.h>
#include "secret.h"
using namespace std;
const int MAXN = 1010;

int N, ans[MAXN][MAXN];

void divide_and_conquer(int l, int r)
{
	if(r - l <= 1)	return;
	
	int mid = (l + r) >> 1;

	for(int i = mid - 1; l <= i; i--)	ans[i][mid] = Secret(ans[i][i], ans[i + 1][mid]);
	for(int i = mid + 2; i <= r; i++)	ans[mid][i] = Secret(ans[mid][i - 1], ans[i][i]);

	divide_and_conquer(l, mid);
	divide_and_conquer(mid + 1, r);	
}

void Init(int n, int a[])
{
	N = n;
	for(int i = 0; i < n; i++)	ans[i][i] = a[i];
	divide_and_conquer(0, N - 1);
}

int findAns(int l, int r, int L, int R)
{
	int mid = (l + r) >> 1;

	if(L <= mid && mid + 1 <= R)	return Secret(ans[L][mid], ans[mid + 1][R]);
	if(R <= mid)	return findAns(l, mid, L, R);
	else			return findAns(mid + 1, r, L, R);
}

int Query(int l, int r)
{
	if(r - l <= 1)	return Secret(ans[l][l], ans[r][r]);
	return findAns(0, N - 1, l, r);
}

• Subtask 1: 0 / 100