Submission #553437

#	Time	Username	Problem	Language	Result	Execution time	Memory
553437		Hanksburger	Secret (JOI14_secret)	C++17	100 / 100	471 ms	8464 KiB

secret

#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
int sum[1005][1005], val[1005], num;
void recur(int l, int r)
{
	if (l==r)
	{
		sum[l][l]=val[l];
		return;
	}
	int mid=(l+r)/2;
	sum[mid][mid]=val[mid];
	sum[mid+1][mid+1]=val[mid+1];
	for (int i=mid-1; i>=l; i--)
		sum[mid][i]=Secret(val[i], sum[mid][i+1]);
	for (int i=mid+2; i<=r; i++)
		sum[mid+1][i]=Secret(sum[mid+1][i-1], val[i]);
	recur(l, mid);
	recur(mid+1, r);
}
void Init(int n, int a[])
{
	num=n;
	for (int i=0; i<n; i++)
		val[i]=a[i];
	recur(0, n-1);
}
int Query(int l, int r)
{
	int a=0, b=num-1;
	while (a<b)
	{
		int mid=(a+b)/2;
		if (l<=mid && mid<r)
			return Secret(sum[mid][l], sum[mid+1][r]);
		else if (r<=mid)
			b=mid;
		else
			a=mid+1;
	}
	return sum[a][a];
}

• Subtask 1: 100 / 100