oj.uz

Submission #76523

# Submission time Handle Problem Language Result Execution time Memory
76523 2018-09-14T12:09:04 Z Noam527 Secret (JOI14_secret) C++14
100 / 100
 655 ms 6096 KB 
#include "secret.h"
#include <bits/stdc++.h>
#define endl '\n'
#define debug cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll hs = 199, inf = 1e18;
const ldb eps = 1e-9, pi = acos(-1);
using namespace std;
/*
int Secret(int X, int Y) {
	cout << "? " << X << " " << Y << endl;
	int rtn;
	cin >> rtn;
	return rtn;
}
*/

map<pair<int, int>, int> ANS;

bool calced(int l, int r) {
	return ANS.count({ l, r });
}

int n;
vector<int> a;

int S(int l, int r) {
	if (l == r) return a[l];
	if (calced(l, r)) return ANS[{l, r}];
	if (calced(l, r - 1)) return ANS[{l, r}] = Secret(ANS[{l, r - 1}], a[r]);
	return ANS[{l, r}] = Secret(a[l], ANS[{l + 1, r}]);
}

void preprocess(int l, int r) {
	if (l == r) return;
	int mid = (l + r) / 2;
	for (int i = mid + 1; i <= r; i++)
		S(mid + 1, i);
	for (int i = mid; i >= l; i--)
		S(i, mid);
	preprocess(l, mid);
	preprocess(mid + 1, r);
}

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

int query(int l, int r, int ql, int qr) {
	int mid = (l + r) / 2;
	if (qr <= mid) return query(l, mid, ql, qr);
	if (mid + 1 <= ql) return query(mid + 1, r, ql, qr);
	return Secret(S(ql, mid), S(mid + 1, qr));
}

int Query(int L, int R) {
	if (L == R) return a[L];
	return query(0, n - 1, L, R);
}
/*
int main() {
	int nn;
	cin >> nn;
	int *A = new int[nn];
	for (int i = 0; i < nn; i++) cin >> A[i];
	Init(nn, A);
	while (1) {
		cout << "your query: ";
		int l, r;
		cin >> l >> r;
		cout << "my answer: " << Query(l, r) << endl;
	}
}
*/

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 2684 KB Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1
2 Correct 178 ms 2852 KB Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1
3 Correct 178 ms 3048 KB Output is correct - number of calls to Secret by Init = 3101, maximum number of calls to Secret by Query = 1
4 Correct 613 ms 5220 KB Output is correct - number of calls to Secret by Init = 6989, maximum number of calls to Secret by Query = 1
5 Correct 603 ms 5480 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
6 Correct 609 ms 5676 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
7 Correct 638 ms 5944 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
8 Correct 637 ms 5944 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
9 Correct 625 ms 6096 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
10 Correct 655 ms 6096 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1