oj.uz

Submission #376324

# Submission time Handle Problem Language Result Execution time Memory
376324 2021-03-11T08:37:20 Z cheissmart Secret (JOI14_secret) C++14
100 / 100
 524 ms 4588 KB 
#include "secret.h"
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 1005;

int n, *a;
int t[N][11];

void build(int l = 0, int r = n, int depth = 0) {
	if(r - l == 1) return;
	int m = (l + r) / 2;
	t[m - 1][depth] = a[m - 1];
	for(int i = m - 2; i >= l; i--)
		t[i][depth] = Secret(a[i], t[i + 1][depth]);
	t[m][depth] = a[m];
	for(int i = m + 1; i < r; i++)
		t[i][depth] = Secret(t[i - 1][depth], a[i]);
	build(l, m, depth + 1);
	build(m, r, depth + 1);
}

void Init(int N, int A[]) {
	n = N, a = A;
	build(0, n);
}

int qry(int l, int r, int tl = 0, int tr = n, int depth = 0) {
	int tm = (tl + tr) / 2;
	if(l < tm && r >= tm) return Secret(t[l][depth], t[r][depth]);
	else if(r < tm) return qry(l, r, tl, tm, depth + 1);
	else return qry(l, r, tm, tr, depth + 1);
}

int Query(int l, int r) {
	if(l == r) return a[l];
	return qry(l, r);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 2540 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 141 ms 2540 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 169 ms 2688 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 506 ms 4588 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 524 ms 4460 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 511 ms 4460 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 518 ms 4460 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 513 ms 4460 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 506 ms 4588 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 522 ms 4460 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1