oj.uz

Submission #284205

# Submission time Handle Problem Language Result Execution time Memory
284205 2020-08-27T02:45:59 Z ChrisT Secret (JOI14_secret) C++17
100 / 100
 517 ms 8696 KB 
#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
const int MN = 1e3 + 5;
int pre[MN][MN], suf[MN][MN], a[MN], n, ops;
void Init (int N, int *arr) {
	n=N;
	for (int i = 0; i < n; i++) a[i] = arr[i];
	function<void(int,int)> build = [&] (int l, int r) {
		if (l>=r) return;
		int mid = (l + r + 1) / 2;
		pre[mid][mid] = a[mid];
		suf[mid][mid-1] = a[mid-1];
		for (int i = mid+1; i <= r; i++) pre[mid][i] = Secret(pre[mid][i-1],a[i]);
		for (int i = mid-2; i >= l; i--) suf[mid][i] = Secret(a[i],suf[mid][i+1]);
		build(l,mid-1); build(mid+1,r);
	};
	build(0,n-1);
}
int query (int l, int r, int ql, int qr) {
	int mid = (l + r + 1) / 2;
	if (qr < mid - 1) return query(l,mid-1,ql,qr);
	if (ql > mid) return query(mid+1,r,ql,qr);
	if (ql == mid) return pre[mid][qr];
	if (qr == mid-1) return suf[mid][ql];
	return Secret(suf[mid][ql],pre[mid][qr]);
}
int Query (int L, int R) {
	if (L == R) return a[L];
	return query(0,n-1,L,R);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 4600 KB Output is correct - number of calls to Secret by Init = 3331, maximum number of calls to Secret by Query = 1
2 Correct 149 ms 4600 KB Output is correct - number of calls to Secret by Init = 3339, maximum number of calls to Secret by Query = 1
3 Correct 161 ms 4644 KB Output is correct - number of calls to Secret by Init = 3347, maximum number of calls to Secret by Query = 1
4 Correct 517 ms 8568 KB Output is correct - number of calls to Secret by Init = 7467, maximum number of calls to Secret by Query = 1
5 Correct 512 ms 8568 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
6 Correct 505 ms 8440 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
7 Correct 516 ms 8496 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
8 Correct 505 ms 8696 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
9 Correct 503 ms 8440 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
10 Correct 510 ms 8568 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1