Submission #852515

#	Time	Username	Problem	Language	Result	Execution time	Memory
852515		Ammar	Secret (JOI14_secret)	C++17	0 / 100	385 ms	4688 KiB

secret

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

int t[10][1001],msk[1001],b[1001];

void build(int x, int l, int r, int a[])
{
	if(l>=r)return;
	int mid=(l+r)/2;
	t[x][mid]=a[mid];
	for(int i=mid-1;i>=l;i--)
		t[x][i]=Secret(a[i],t[x][i+1]);
	
	t[x][mid+1]=a[mid+1];
	for(int i=mid+2;i<=r;i++)
	{
		t[x][i]=Secret(t[x][i-1],a[i]);
		msk[i]|=(1<<x);
	}
	build(x+1,l,mid,a);
	build(x+1,mid+1,r,a);
}

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

int Query(int l, int r)
{
	if(l==r)return b[l];
	int z=__builtin_ctz(msk[l]^msk[r]);
	return Secret(t[z][l],t[z][r]);
}

• Subtask 1: 0 / 100