oj.uz

Submission #314346

# Submission time Handle Problem Language Result Execution time Memory
314346 2020-10-19T18:23:28 Z LucaDantas Secret (JOI14_secret) C++17
100 / 100
 520 ms 8572 KB 
#include "secret.h"
#include<bits/stdc++.h>
using namespace std;

using pii = pair<int,int>;

#define ff first
#define ss second

constexpr int maxn = 1e3+10;

int a[maxn], n;

struct SegmentTree
{
	int pref[4*maxn][maxn], suf[4*maxn][maxn];
	void build(int node, int i, int j) {
		if(j - i <= 1) return;
		int m = (i+j) >> 1;

		pref[node][m] = a[m];
		for(int pos = m-1; pos >= i; pos--)
			pref[node][pos] = Secret(a[pos], pref[node][pos+1]);

		suf[node][m+1] = a[m+1];
		for(int pos = m+2; pos <= j; pos++)
			suf[node][pos] = Secret(suf[node][pos-1], a[pos]);

		build(2*node, i, m); build(2*node+1, m+1, j);
	}
	int query(int node, int i, int j, int l, int r) {
		if(i == j) return a[i];
		if(i+1 == j) return Secret(a[i], a[j]);
		int m = (i+j) >> 1;
		if(r <= m) return query(2*node, i, m, l, r);
		if(l > m) return query(2*node+1, m+1, j, l, r);
		return Secret(pref[node][l], suf[node][r]);
	}
} seg;

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

int Query(int L, int R) {
	if(L == R) return a[L];
	return seg.query(1, 0, n, L, R);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 4604 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
2 Correct 143 ms 4472 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
3 Correct 146 ms 4656 KB Output is correct - number of calls to Secret by Init = 3604, maximum number of calls to Secret by Query = 1
4 Correct 504 ms 8568 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
5 Correct 520 ms 8568 KB Output is correct - number of calls to Secret by Init = 7987, maximum number of calls to Secret by Query = 1
6 Correct 509 ms 8456 KB Output is correct - number of calls to Secret by Init = 7987, maximum number of calls to Secret by Query = 1
7 Correct 508 ms 8572 KB Output is correct - number of calls to Secret by Init = 7987, maximum number of calls to Secret by Query = 1
8 Correct 510 ms 8568 KB Output is correct - number of calls to Secret by Init = 7987, maximum number of calls to Secret by Query = 1
9 Correct 508 ms 8440 KB Output is correct - number of calls to Secret by Init = 7987, maximum number of calls to Secret by Query = 1
10 Correct 510 ms 8572 KB Output is correct - number of calls to Secret by Init = 7987, maximum number of calls to Secret by Query = 1