oj.uz

Submission #29096

# Submission time Handle Problem Language Result Execution time Memory
29096 2017-07-18T08:40:58 Z PrOAhMeT Secret (JOI14_secret) C++14
100 / 100
 659 ms 9924 KB 
#include "secret.h"
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define LL long long
#define st first
#define nd second
#define endl '\n'
using namespace std;

int a[1001][1001],size;

void dac(int l,int r,int v[]) {

	if(l>r)
		return;
	if(l==r) {
		a[l][l]=v[l];
		return;
	}
	int md=(l+r)/2;
	a[md][md]=v[md];
	for(int i=md-1;i>=l;--i) {
		a[i][md]=Secret(v[i],a[i+1][md]);
	}
	if(md!=r) {
		a[md+1][md+1]=v[md+1];
		for(int i=md+2;i<=r;++i){
			a[md+1][i]=Secret(a[md+1][i-1],v[i]);
		}
	}
	dac(l,md-1,v);
	dac(md+1,r,v);

}

int solve(int l,int r,int ll,int rr) {

	int md=(l+r)/2;
	if(ll<=md&&rr>=md) {
		if(rr==md)
			return a[ll][md];
		else return Secret(a[ll][md],a[md+1][rr]);
	}
	if(rr<md)
		return solve(l,md-1,ll,rr);
	else return solve(md+1,r,ll,rr);

}

void Init(int N, int A[]) {
  
  size=N;
	dac(0,N-1,A);

}

int Query(int L, int R) {

	return solve(0,size-1,L,R);

}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 9924 KB Output is correct - number of calls to Secret by Init = 3331, maximum number of calls to Secret by Query = 1
2 Correct 176 ms 9924 KB Output is correct - number of calls to Secret by Init = 3339, maximum number of calls to Secret by Query = 1
3 Correct 179 ms 9924 KB Output is correct - number of calls to Secret by Init = 3347, maximum number of calls to Secret by Query = 1
4 Correct 659 ms 9924 KB Output is correct - number of calls to Secret by Init = 7467, maximum number of calls to Secret by Query = 1
5 Correct 636 ms 9924 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
6 Correct 609 ms 9924 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
7 Correct 619 ms 9924 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
8 Correct 603 ms 9924 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
9 Correct 636 ms 9924 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
10 Correct 619 ms 9924 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1