oj.uz

Submission #112867

# Submission time Handle Problem Language Result Execution time Memory
112867 2019-05-22T10:46:16 Z Anai Secret (JOI14_secret) C++14
100 / 100
 516 ms 4696 KB 
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 1005;

vector<int> pom[N * 4];
int v[N];

int n, ql, qr;


static inline void build(int nod, int st, int dr) {
	if (st == dr) {
		pom[nod] = {v[st]};
		return; }
	int mid = (st + dr) / 2;

	build(2 * nod, st, mid);
	build(2 * nod + 1, mid + 1, dr);

	pom[nod].resize(dr - st + 1);
	pom[nod][mid - st] = v[mid];
	pom[nod][mid + 1 - st] = v[mid + 1];
	for (int i = mid + 2; i <= dr; ++i)
		pom[nod][i - st] = Secret(pom[nod][i - 1 - st], v[i]);
	for (int i = mid - 1; i >= st; --i)
		pom[nod][i - st] = Secret(v[i], pom[nod][i + 1 - st]); }

static int query(int nod, int st, int dr) {
	if (ql == qr)
		return v[ql];
	int mid = (st + dr) / 2;
	if (ql <= mid && mid < qr)
		return Secret(pom[nod][ql - st], pom[nod][qr - st]);
	if (qr <= mid)
		return query(2 * nod, st, mid);
	else
		return query(2 * nod + 1, mid + 1, dr); }

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

int Query(int L, int R) {
	ql = L, qr = R;
	return query(1, 0, n - 1); }

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 2680 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 144 ms 2604 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 142 ms 2632 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 494 ms 4648 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 492 ms 4572 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 505 ms 4568 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 516 ms 4608 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 512 ms 4564 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 4624 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 509 ms 4696 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1