oj.uz

Submission #141159

# Submission time Handle Problem Language Result Execution time Memory
141159 2019-08-07T04:45:10 Z babo Secret (JOI14_secret) C++14
100 / 100
 601 ms 4596 KB 
//#include "secret.h"
#include <bits/stdc++.h>

void Init(int N, int A[]);
int Query(int L, int R);

int Secret(int X, int Y);

int tr[20][2020];
int a[2020];
int n;

void bin(int now,int s,int e){
	int i,sum;
	int mid=(s+e)/2;
	for(i=mid,sum=a[mid];i<e;i++)
	{
		tr[now][i]=sum;
		if(i+1<e)
			sum=Secret(sum,a[i+1]);
	}
	for(i=mid-1,sum=a[mid-1];i>=s;i--)
	{
		tr[now][i]=sum;
		if(i-1>=s)
			sum=Secret(a[i-1],sum);
	}

	if(e<=s+2)
		return;
	bin(now+1,s,mid);
	bin(now+1,mid,e);
}

void Init(int N,int A[]){
	n=N;
	for(int i=0;i<n;i++)
		a[i]=A[i];
	bin(1,0,n);
	/*for(int i=1;i<=9;i++)
	{
		for(int j=0;j<N;j++)
		{
			printf("%d ",tr[i][j]);
		}
		puts("");
	}*/

}

int bin2(int now,int s,int e,int l,int r){
	int mid=(s+e)/2;
	if(s>r||e<l) return -1;
	if(l<=mid&&r>=mid)
	{
		if(l==mid) return tr[now][r-1];
		if(r==mid) return tr[now][l];
		return Secret(tr[now][l],tr[now][r-1]);
	}
	int temp1=bin2(now+1,s,mid,l,r);
	int temp2=bin2(now+1,mid,e,l,r);
	//printf("%d %d %d %d %d: %d\n",now,s,e,l,r,temp1==-1?temp2:temp1);
	if(temp1==-1) return temp2;
	return temp1;
}


int Query(int l,int r){
	return bin2(1,0,n,l,r+1);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 2604 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 172 ms 2596 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 171 ms 2588 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 599 ms 4596 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 595 ms 4492 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 597 ms 4456 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 600 ms 4448 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 599 ms 4412 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 599 ms 4464 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 601 ms 4516 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1