oj.uz

Submission #36541

# Submission time Handle Problem Language Result Execution time Memory
36541 2017-12-10T11:54:52 Z IvanC Secret (JOI14_secret) C++14
100 / 100
 659 ms 9996 KB 
#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
const int MAXN = 1010;
int V[MAXN],P[MAXN][MAXN],n;
void precalc(int l,int r){
	if(l == r){
		P[l][l] = V[l];
		return;
	}
	int m = (l+r)/2;
	precalc(l,m);
	precalc(m+1,r);
	for(int i = m;i>=l;i--){
		if(P[i][m] == -1){
			P[i][m] = Secret(V[i],P[i+1][m]);
		}
	}
	for(int i = m + 1;i<=r;i++){
		if(P[m+1][i] == -1){
			P[m+1][i] = Secret(P[m+1][i-1],V[i]);
		}
	}
}
void Init(int N,int A[]){
	n = N;
	for(int i = 1;i<=n;i++){
		V[i] = A[i-1];
	}
	memset(P,-1,sizeof(P));
	precalc(1,n);
}
int Query(int L,int R){
	L++;
	R++;
	for(int i = L;i+1<=R;i++){
		if(P[L][i] != -1 && P[i+1][R] != -1){
			return Secret(P[L][i],P[i+1][R]);
		}
	}
	return P[L][R];
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 9996 KB Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1
2 Correct 179 ms 9996 KB Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1
3 Correct 176 ms 9996 KB Output is correct - number of calls to Secret by Init = 3101, maximum number of calls to Secret by Query = 1
4 Correct 626 ms 9996 KB Output is correct - number of calls to Secret by Init = 6989, maximum number of calls to Secret by Query = 1
5 Correct 623 ms 9996 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
6 Correct 646 ms 9996 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
7 Correct 636 ms 9996 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
8 Correct 643 ms 9996 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
9 Correct 659 ms 9996 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
10 Correct 619 ms 9996 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1