oj.uz

Submission #296222

# Submission time Handle Problem Language Result Execution time Memory
296222 2020-09-10T12:24:01 Z patrikpavic2 Secret (JOI14_secret) C++17
100 / 100
 591 ms 8800 KB 
#include "secret.h"
#include <cstring>

const int N = 1e3 + 50;

int n, A[N], Q[N][N];

void calc(int l, int r){
	if(l + 2 > r) return;
	int mid = (l + r) / 2;
	for(int i = mid - 1;i >= l;i--)
		Q[i][mid] = Secret(A[i], Q[i + 1][mid]);
	for(int i = mid + 2;i <= r;i++)
		Q[mid + 1][i] = Secret(Q[mid + 1][i - 1], A[i]);
	calc(l, mid);
	calc(mid + 1, r);
}

void Init(int nn, int AA[]) {
	n = nn; memset(Q, -1, sizeof(Q));
	for(int i = 0;i < n;i++){
		A[i] = AA[i]; Q[i][i] = A[i];
	}
	calc(0, n - 1);
}

int Query(int l, int r) {
	if(Q[l][r] != -1)
		return Q[l][r];
	for(int k = l;k < r;k++){
		if(Q[l][k] != -1 && Q[k + 1][r] != -1)
			return Secret(Q[l][k], Q[k + 1][r]);
	}
	return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 6776 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 158 ms 6776 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 151 ms 6776 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 551 ms 8720 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 591 ms 8736 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 556 ms 8640 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 540 ms 8696 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 538 ms 8624 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 548 ms 8800 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 554 ms 8756 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1