oj.uz

Submission #25250

# Submission time Handle Problem Language Result Execution time Memory
25250 2017-06-21T04:42:47 Z khsoo01 Secret (JOI14_secret) C++11
100 / 100
 673 ms 5152 KB 
#include "secret.h"
int n, a[1005], dt[10][1005];

void solve (int S, int E, int X) {
	if(S == E) return;
	int M = (S+E)/2;
	dt[X][M] = a[M];
	for(int i=M-1;i>=S;i--) {
		dt[X][i] = Secret(a[i], dt[X][i+1]);
	}
	dt[X][M+1] = a[M+1];
	for(int i=M+2;i<=E;i++) {
		dt[X][i] = Secret(dt[X][i-1], a[i]);
	}
	solve(S, M, X+1);
	solve(M+1, E, X+1);
}

int get (int S, int E, int SS, int SE, int X) {
	int M = (SS+SE)/2;
	if(E <= M) return get(S, E, SS, M, X+1);
	if(S > M) return get(S, E, M+1, SE, X+1);
	return Secret(dt[X][S], dt[X][E]);
}

void Init(int N, int A[]) {
	n = N;
	for(int i=0;i<n;i++) a[i] = A[i];
	solve(0, n-1, 0);
}

int Query(int L, int R) {
	if(L == R) return a[L];
	return get(L, R, 0, n-1, 0);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 5152 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 169 ms 5152 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 179 ms 5152 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 619 ms 5152 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 623 ms 5152 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 616 ms 5152 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 636 ms 5152 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 623 ms 5152 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 626 ms 5152 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 673 ms 5152 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1