oj.uz

Submission #361246

# Submission time Handle Problem Language Result Execution time Memory
361246 2021-01-28T22:05:56 Z ogibogi2004 Secret (JOI14_secret) C++14
100 / 100
 536 ms 4588 KB 
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1024;
int a[MAXN],n;
int pre[MAXN][MAXN];
void dq(int l,int r,int d)
{
	if(l+1==r)return;
	if(l==r)return;
	int mid=(l+r)/2;
	pre[d][mid]=a[mid];
	for(int i=mid-1;i>=l;i--)pre[d][i]=Secret(a[i],pre[d][i+1]);
	pre[d][mid+1]=a[mid+1];
	for(int i=mid+2;i<=r;i++)pre[d][i]=Secret(pre[d][i-1],a[i]);
	dq(l,mid,d+1);dq(mid+1,r,d+1);
}
void Init(int N, int A[]) {
	for(int i=0;i<N;i++)a[i]=A[i];
	dq(0,N-1,0);n=N;
}
int dq_query(int l,int r,int l1,int r1,int d)
{
	int mid=(l+r)/2;
	if(l1<=mid&&r1>mid)
	{
		return Secret(pre[d][l1],pre[d][r1]);
	}
	if(r1==mid)return pre[d][l1];
	if(r1<=mid)return dq_query(l,mid,l1,r1,d+1);
	else return dq_query(mid+1,r,l1,r1,d+1);
}
int Query(int L, int R) {
	if(L==R)return a[L];
	if(L+1==R)return Secret(a[L],a[R]);
	return dq_query(0,n-1,L,R,0);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 2496 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 145 ms 2540 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 145 ms 2668 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 505 ms 4332 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 499 ms 4460 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 505 ms 4340 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 536 ms 4492 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 518 ms 4472 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 523 ms 4332 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 506 ms 4588 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1