oj.uz

Submission #68561

# Submission time Handle Problem Language Result Execution time Memory
68561 2018-08-17T10:29:53 Z chpipis Secret (JOI14_secret) C++11
100 / 100
 694 ms 8544 KB 
#include "secret.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1005;
const int LOGN = 10;

int n, ar[MAXN];
int st[MAXN << 2][MAXN];

#define housekeep int mid = (L + R) >> 1, left = p << 1, right = left | 1

void build(int p, int L, int R) {
	if (L == R) return;
	housekeep;
	st[p][mid] = ar[mid];
	for (int i = mid - 1; i >= L; i--)
		st[p][i] = Secret(ar[i], st[p][i + 1]);
	st[p][mid + 1] = ar[mid + 1];
	for (int i = mid + 2; i <= R; i++)
		st[p][i] = Secret(st[p][i - 1], ar[i]);
	build(left, L, mid);
	build(right, mid + 1, R);
}

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

int ask(int p, int L, int R, int i, int j) {
	housekeep;

	if (i <= mid && j >= mid + 1) {
		return Secret(st[p][i], st[p][j]);
	}

	if (j <= mid)
		return ask(left, L, mid, i, j);
	else
		return ask(right, mid + 1, R, i, j);
}

int Query(int L, int R) {
	if (L == R) return ar[L];
	return ask(1, 0, n - 1, L, R);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 4616 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 173 ms 4616 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 176 ms 4616 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 629 ms 8492 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 671 ms 8492 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 645 ms 8544 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 647 ms 8544 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 694 ms 8544 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 684 ms 8544 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 639 ms 8544 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1