oj.uz

Submission #117536

# Submission time Handle Problem Language Result Execution time Memory
117536 2019-06-16T13:02:07 Z tjd229 Secret (JOI14_secret) C++14
100 / 100
 605 ms 8388 KB 
#include "secret.h"
int range[1000][1000];
int _A[1000], _N;
void pre(int s, int e) {
	if (s >= e) return;
	int m = (s + e) >> 1;
	for (int i = m - 1; i >= s; --i)
		range[i][m] = Secret(_A[i],range[i+1][m]);
	pre(s, m - 1);
	++m;
	for (int i = m + 1; i <= e; ++i)
		range[m][i] = Secret(range[m][i - 1], _A[i]);
	pre(m+1,e);
}
void Init(int N, int A[]) {
	_N = N;
	for (int i = 0; i < N; ++i) _A[i] =range[i][i]= A[i];
	pre(0, N - 1);
}
int op(int s,int e,int l,int r) {
	int m = (s+e)>>1;
	if (m <= r && m + 1 >= l) {
		if (r == m || m+1==l) return range[l][r];
		return Secret(range[l][m],range[m+1][r]);
	}
	if (m > r) return op(s,m-1,l,r);
	else return op(m + 2, e, l, r);
}
int Query(int L, int R) {
	if (L == R) return _A[L];
	else if (L + 1 == R) return Secret(_A[L], _A[R]);
	return op(0,_N-1,L,R);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 4400 KB Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1
2 Correct 140 ms 4340 KB Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1
3 Correct 144 ms 4344 KB Output is correct - number of calls to Secret by Init = 3100, 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 = 6988, maximum number of calls to Secret by Query = 1
5 Correct 605 ms 8388 KB Output is correct - number of calls to Secret by Init = 6996, 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 = 6996, maximum number of calls to Secret by Query = 1
7 Correct 485 ms 8156 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
8 Correct 488 ms 8180 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
9 Correct 482 ms 8312 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
10 Correct 480 ms 8312 KB Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1