Submission #7006

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
7006	2014-07-12T09:26:23 Z	gs13068	Secret (JOI14_secret)	C++	100 / 100	656 ms	169116 KB

secret

#include "secret.h"

static int a[2048];
static int s[20480];
static int e[20480];
int l[20480][1024];
int r[20480][1024];

static void calc(int x)
{
	if(e[x]-s[x]>1)
	{
		int i,j,m=(s[x]+e[x])>>1;
		j=a[m-1];
		l[x][m-1]=j;
		for(i=m-2;i>=s[x];i--)
		{
			j=Secret(a[i],j);
			l[x][i]=j;
		}
		j=a[m];
		r[x][m]=j;
		for(i=m+1;i<e[x];i++)
		{
			j=Secret(j,a[i]);
			r[x][i]=j;
		}
		s[x<<1]=s[x];
		e[x<<1]=m;
		calc(x<<1);
		s[(x<<1)+1]=m;
		e[(x<<1)+1]=e[x];
		calc((x<<1)+1);
	}
}

static int get(int x,int L,int R)
{
	if(L==R)return a[L];
	int m=(s[x]+e[x])>>1;
	if(L<m&&m<=R)return Secret(l[x][L],r[x][R]);
	if(R<m)return get(x<<1,L,R);
	return get((x<<1)+1,L,R);
}

void Init(int N, int A[])
{
	int i;
	for(i=0;i<N;i++)a[i]=A[i];
	s[1]=0;
	e[1]=1000;
    calc(1);
}

int Query(int L, int R)
{
	return get(1,L,R);
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	183 ms	169116 KB	Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
2	Correct	183 ms	169116 KB	Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
3	Correct	183 ms	169116 KB	Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
4	Correct	643 ms	169116 KB	Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
5	Correct	629 ms	169116 KB	Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6	Correct	643 ms	169116 KB	Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7	Correct	653 ms	169116 KB	Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8	Correct	656 ms	169116 KB	Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9	Correct	653 ms	169116 KB	Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10	Correct	629 ms	169116 KB	Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1