Submission #853163

#	Time	Username	Problem	Language	Result	Execution time	Memory
853163		epicci23	Secret (JOI14_secret)	C++17	100 / 100	412 ms	4712 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];
	msk[mid+1]|=(1<<x);
	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: 100 / 100