oj.uz

Submission #301688

# Submission time Handle Problem Language Result Execution time Memory
301688 2020-09-18T06:05:13 Z E869120 Secret (JOI14_secret) C++14
100 / 100
 516 ms 8344 KB 
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;

int N;
int A[1009];
int V[1009][1009];
int Value;

void solve(int cl, int cr) {
	if (cr - cl == 1) return;
	int cm = (cl + cr) / 2;
	
	// LFT
	int cur = A[cm - 1];
	for (int i = cm - 2; i >= cl; i--) {
		cur = Secret(A[i], cur);
		V[i][cm - 1] = cur;
	}
	
	// RHT
	int cur2 = A[cm];
	for (int i = cm + 1; i < cr; i++) {
		cur2 = Secret(cur2, A[i]);
		V[cm][i] = cur2;
	}
	
	// SAIKI
	solve(cl, cm);
	solve(cm, cr);
}

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

void dfs(int l, int r, int a, int b) {
	int m = (a + b) / 2;
	if (r <= a || b <= l) return;
	if (l < m && m < r) {
		int p1 = V[l][m - 1];
		int p2 = V[m][r - 1];
		Value = Secret(p1, p2);
		return;
	}
	dfs(l, r, a, m);
	dfs(l, r, m, b);
}

int Query(int L, int R) {
	if (L == R) return A[L];
	Value = -1;
	dfs(L, R + 1, 0, N);
	return Value;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 4472 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 145 ms 4472 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 147 ms 4468 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 511 ms 8312 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 503 ms 8312 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 516 ms 8216 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 515 ms 8344 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 514 ms 8328 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 513 ms 8312 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 511 ms 8312 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1