oj.uz

Submission #703007

# Submission time Handle Problem Language Result Execution time Memory
703007 2023-02-25T13:40:18 Z NeroZein Secret (JOI14_secret) C++17
100 / 100
 419 ms 8236 KB 
#include "secret.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1003;

int n;
vector<int> a;

int st[N][N];

void solve (int l, int r) {
	if (l == r) {
		return;
	}
	int mid = (l + r) >> 1;
	solve(l, mid); 
	solve(mid+1, r); 
	st[mid][mid] = a[mid];
	for (int i = mid - 1; i >= l; --i) {
		st[i][mid] = Secret(a[i], st[i+1][mid]);
	}
	st[mid+1][mid+1] = a[mid+1];
	for (int i = mid+2; i <= r; ++i) {
		st[mid+1][i] = Secret(st[mid+1][i-1], a[i]);
	}
}

void Init(int N_, int A[]) {
	n = N_;
	a.resize(n);
	for (int i = 0; i < n; i++) a[i] = A[i];
	solve(0, n - 1);
}

int get (int l, int r, int s, int e) {
	if (s == e) {
		return a[s];
	}
	int mid = (l + r) >> 1;
	if (s > mid) {
		return get(mid+1, r, s, e);
	}
	if (e <= mid) {
		return get(l, mid, s, e);
	}
	return Secret(st[s][mid], st[mid+1][e]);
}

int Query(int L, int R) {
	return get(0, n-1, L, R);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 4380 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 119 ms 4404 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 127 ms 4356 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 416 ms 8192 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 417 ms 8124 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 413 ms 8136 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 419 ms 8180 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 409 ms 8144 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 417 ms 8236 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 414 ms 8232 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1