oj.uz

Submission #269323

# Submission time Handle Problem Language Result Execution time Memory
269323 2020-08-17T06:29:21 Z ruler Secret (JOI14_secret) C++14
100 / 100
 539 ms 8440 KB 
#include <bits/stdc++.h>
#include "secret.h"
using namespace std;

const int MAXN = 1e3 + 5;

int n, A[MAXN], DP[MAXN][MAXN];

void Build(int s = 0, int e = n) {
	if (e - s < 2) {
		DP[s][e] = A[s];
		return;
	}
	int md = (s + e) >> 1;
	Build(s, md), Build(md, e);
	DP[md - 1][md] = A[md - 1];
	for (int i = md - 2; i >= s; i--) DP[i][md] = Secret(A[i], DP[i + 1][md]);
	DP[md][md + 1] = A[md];
	for (int i = md + 2; i <= e; i++) DP[md][i] = Secret(DP[md][i - 1], A[i - 1]);
}
int Get(int l, int r, int s = 0, int e = n) {
	int md = (s + e) >> 1;
	if (r < md) return Get(l, r, s, md);
	if (l > md) return Get(l, r, md, e);
	if (r == md) return DP[l][md];
	if (l == md) return DP[md][r];
	return Secret(DP[l][md], DP[md][r]);
}
void Init(int _n, int _A[]) {
	n = _n;
	for (int i = 0; i < n; i++) A[i] = _A[i];
	Build();
}
int Query(int l, int r) {
	return Get(l, r + 1);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 4344 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 146 ms 4364 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 146 ms 4500 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 504 ms 8440 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 515 ms 8360 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 539 ms 8312 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 523 ms 8184 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 516 ms 8184 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 511 ms 8292 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 8184 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1