oj.uz

Submission #52467

# Submission time Handle Problem Language Result Execution time Memory
52467 2018-06-26T04:55:11 Z 윤교준(#1366) Secret (JOI14_secret) C++11
100 / 100
 642 ms 6216 KB 
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
map<pii, int> RC;
int f(int x, int y) {
	auto it = RC.find(pii(x, y));
	if(RC.end() != it) return it -> second;
	return (RC[pii(x, y)] = Secret(x, y));
}

const int MAXN = 1005;

map<pii, int> Q;

int A[MAXN];

int N;

void init(int s, int e) {
	if(s == e) {
		Q[pii(s, e)] = A[s];
		return;
	}

	int m = (s+e) / 2;
	init(s, m); init(m+1, e);

	for(int i = m-1, c = A[m]; s <= i; i--) {
		c = f(A[i], c);
		Q[pii(i, m)] = c;
	}
	for(int i = m+2, c = A[m+1]; i <= e; i++) {
		c = f(c, A[i]);
		Q[pii(m+1, i)] = c;
	}
}

void Init(int N, int A[]) {
	::N = N;
	for(int i = 0; i < N; i++) ::A[i] = A[i];

	init(0, N-1);
}

int get(int s, int e, int p, int q) {
	int m = (s+e) / 2;
	if(p <= m && m+1 <= q) {
		return f(Q[pii(p, m)], Q[pii(m+1, q)]);
	} else if(q <= m) {
		return get(s, m, p, q);
	} else {
		return get(m+1, e, p, q);
	}
}

int Query(int L, int R) {
	if(L == R) return A[L];
	if(L+1 == R) return f(A[L], A[R]);
	return get(0, N-1, L, R);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 3416 KB Output is correct - number of calls to Secret by Init = 3324, maximum number of calls to Secret by Query = 1
2 Correct 182 ms 3428 KB Output is correct - number of calls to Secret by Init = 3332, maximum number of calls to Secret by Query = 1
3 Correct 215 ms 3672 KB Output is correct - number of calls to Secret by Init = 3341, maximum number of calls to Secret by Query = 1
4 Correct 612 ms 6056 KB Output is correct - number of calls to Secret by Init = 7483, maximum number of calls to Secret by Query = 1
5 Correct 604 ms 6088 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
6 Correct 610 ms 6088 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
7 Correct 642 ms 6200 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
8 Correct 605 ms 6200 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
9 Correct 615 ms 6216 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
10 Correct 614 ms 6216 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1