Submission #321493

#	Time	Username	Problem	Language	Result	Execution time	Memory
321493		Lawliet	Secret (JOI14_secret)	C++17	100 / 100	514 ms	8428 KiB

secret

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

using namespace std;

const int MAXN = 1010;

int n;

int v[MAXN];
int value[MAXN][MAXN];

int getBreak(int l, int r, int lQuery, int rQuery)
{
	int mid = ( l + r )/2;

	if( lQuery <= mid && mid + 1 <= rQuery ) return mid;

	if( rQuery <= mid ) return getBreak( l , mid , lQuery , rQuery );
	return getBreak( mid + 1 , r , lQuery , rQuery );
}

void DivAndConquer(int l, int r)
{
	if( l == r ) return;

	int mid = ( l + r )/2;

	DivAndConquer( l , mid );
	DivAndConquer( mid + 1 , r );

	for(int t = mid - 1 ; t >= l ; t--)
		value[t][mid] = Secret( v[t] , value[t + 1][mid] );

	for(int t = mid + 2 ; t <= r ; t++)
		value[mid + 1][t] = Secret( value[mid + 1][t - 1] , v[t] );
}

void Init(int N, int A[]) 
{
	n = N;

	for(int i = 0 ; i < n ; i++)
		v[i] = A[i], value[i][i] = A[i];

	DivAndConquer( 0 , n - 1 );
}

int Query(int L, int R)
{
	if( L == R ) return v[L];

	int t = getBreak( 0 , n - 1 , L , R );
	return Secret( value[L][t] , value[t + 1][R] );
}

• Subtask 1: 100 / 100