Submission #751471

# Submission time Handle Problem Language Result Execution time Memory
751471 2023-05-31T15:38:07 Z jmyszka2007 Secret (JOI14_secret) C++17
100 / 100
509 ms 6464 KB
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
int res[1010][1010];
int tab[1010];
int N;
void cnt(int l, int r) {
	if(l >= r) {
		return;
	}
	int mid = (l + r) / 2;
	res[mid][mid] = tab[mid];
	res[mid][mid - 1] = tab[mid - 1];
	for(int i = mid - 2; i >= l; i--) {
		res[mid][i] = Secret(tab[i], res[mid][i + 1]);
	}
	for(int i = mid + 1; i <= r; i++) {
		res[mid][i] = Secret(res[mid][i - 1], tab[i]);
	}
	cnt(l, mid - 1);
	cnt(mid + 1, r);
}
void Init(int n, int a[]) {
	N = n;
	for(int i = 0; i < n; i++) {
		tab[i] = a[i];
	}
	cnt(0, n - 1);
}
int rek(int l, int r, int L, int R) {
	if(l == r) {
		return tab[l];
	}
	int mid = (L + R) / 2;
	if(l <= mid && mid <= r) {
		if(l == mid) {
			return res[mid][r];
		}
		return Secret(res[mid][l], res[mid][r]);
	}
	if(l > mid) {
		return rek(l, r, mid + 1, R);
	}
	return rek(l, r, L, mid - 1);
}
int Query(int l, int r) {
	return rek(l, r, 0, N - 1);
}
# Verdict Execution time Memory Grader output
1 Correct 143 ms 3416 KB Output is correct - number of calls to Secret by Init = 3331, maximum number of calls to Secret by Query = 1
2 Correct 137 ms 3332 KB Output is correct - number of calls to Secret by Init = 3340, maximum number of calls to Secret by Query = 1
3 Correct 129 ms 3392 KB Output is correct - number of calls to Secret by Init = 3349, maximum number of calls to Secret by Query = 1
4 Correct 476 ms 6232 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
5 Correct 477 ms 6264 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
6 Correct 455 ms 6308 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
7 Correct 469 ms 6240 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
8 Correct 504 ms 6348 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
9 Correct 509 ms 6284 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1
10 Correct 466 ms 6464 KB Output is correct - number of calls to Secret by Init = 7499, maximum number of calls to Secret by Query = 1