oj.uz

Submission #137047

# Submission time Handle Problem Language Result Execution time Memory
137047 2019-07-27T02:30:17 Z mosesmayer Secret (JOI14_secret) C++17
0 / 100
 594 ms 9384 KB 
#include "secret.h"
#include <map>
using namespace std;

int spt[10][1005];
int a[1005];
map<pair<int,int>, int> asked;
int ask(int x, int y){
	pair<int, int> u = make_pair(x, y);
	if (asked.find(u) != asked.end()) return asked[u];
	return asked[u] = Secret(x, y);
}
void rec(int l, int r, int d = 0){
	if (l == r){
		spt[d][l] = a[l];
		return;
	}
	int md = (l + r) >> 1;
	rec(l, md, d + 1); rec(md + 1, r, d + 1);
	int prv = a[md];
	spt[d][md] = a[md];
	for (int i = md - 1; i >= l; --i){
		spt[d][i] = ask(a[i], prv);
		prv = spt[d][i];
	}
	prv = a[md + 1];
	spt[d][md + 1] = a[md + 1];
	for (int i = md + 2; i <= r; i++){
		spt[d][i] = ask(prv, a[i]);
		prv = spt[d][i];
	}
}
int n;
void Init(int N, int A[]){
	n = N;
	for (int i = 0; i < N; i++) a[i] = A[i];
	rec(0, N - 1);
}

int ans(int i, int j, int l, int r, int d = 0){
	if (l == r) return spt[d][l];
	int md = (l + r) >> 1;
	if (j <= md) return ans(i, j, l, md, d + 1);
	else if (i >= md + 1) return ans(i, j, md+1, r, d+1);
	else {
		return ask(spt[d][i], spt[d][j]);
	}
}
int Query(int L, int R){
	return ans(L, R, 0, n - 1);
	return 0;
}

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 3320 KB Output is correct - number of calls to Secret by Init = 3324, maximum number of calls to Secret by Query = 1
2 Correct 177 ms 3304 KB Output is correct - number of calls to Secret by Init = 3332, maximum number of calls to Secret by Query = 1
3 Correct 177 ms 3172 KB Output is correct - number of calls to Secret by Init = 3341, maximum number of calls to Secret by Query = 1
4 Runtime error 588 ms 9352 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 592 ms 9324 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 588 ms 9340 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 594 ms 9384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 590 ms 9208 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 591 ms 9260 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 592 ms 9300 KB Execution killed with signal 11 (could be triggered by violating memory limits)