oj.uz

Submission #605826

# Submission time Handle Problem Language Result Execution time Memory
605826 2022-07-26T03:01:25 Z SanguineChameleon Secret (JOI14_secret) C++14
100 / 100
 465 ms 8328 KB 
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;

const int ms = 1e3 + 20;
int n;
int a[ms];
int res[ms][ms];

void build(int lt, int rt) {
	if (lt == rt) {
		res[lt][lt] = a[lt];
		return;
	}
	int mt = (lt + rt) / 2;
	if (lt <= mt - 1) {
		res[mt - 1][mt - 1] = a[mt - 1];
		for (int i = mt - 2; i >= lt; i--) {
			res[i][mt - 1] = Secret(a[i], res[i + 1][mt - 1]);
		}
		build(lt, mt - 1);
	}
	res[mt][mt] = a[mt];
	if (mt + 1 <= rt) {
		for (int i = mt + 1; i <= rt; i++) {
			res[mt][i] = Secret(res[mt][i - 1], a[i]);
		}
		build(mt + 1, rt);
	}
}

int solve(int lt, int rt, int ql, int qr) {
	int mt = (lt + rt) / 2;
	if (ql == mt) {
		return res[mt][qr];
	}
	if (ql < mt && mt <= qr) {
		return Secret(res[ql][mt - 1], res[mt][qr]);
	}
	if (qr < mt) {
		return solve(lt, mt - 1, ql, qr);
	}
	return solve(mt + 1, rt, ql, qr);
}

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

int Query(int L, int R) {
	return solve(0, n - 1, L, R);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 4412 KB Output is correct - number of calls to Secret by Init = 3331, maximum number of calls to Secret by Query = 1
2 Correct 122 ms 4408 KB Output is correct - number of calls to Secret by Init = 3340, maximum number of calls to Secret by Query = 1
3 Correct 121 ms 4352 KB Output is correct - number of calls to Secret by Init = 3349, maximum number of calls to Secret by Query = 1
4 Correct 459 ms 8264 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
5 Correct 429 ms 8264 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
6 Correct 447 ms 8288 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
7 Correct 459 ms 8328 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
8 Correct 465 ms 8224 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
9 Correct 438 ms 8280 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
10 Correct 450 ms 8272 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1