oj.uz

답안 #137048

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
137048 2019-07-27T02:34:31 Z mosesmayer 비밀 (JOI14_secret) C++17
100 / 100
 610 ms 5748 KB 
#include "secret.h"
#include <map>
using namespace std;

int spt[15][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
100.0 / 100.0

# 결과 실행 시간 메모리 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 3252 KB Output is correct - number of calls to Secret by Init = 3332, maximum number of calls to Secret by Query = 1
3 Correct 176 ms 3192 KB Output is correct - number of calls to Secret by Init = 3341, maximum number of calls to Secret by Query = 1
4 Correct 603 ms 5460 KB Output is correct - number of calls to Secret by Init = 7483, maximum number of calls to Secret by Query = 1
5 Correct 607 ms 5468 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
6 Correct 607 ms 5440 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
7 Correct 610 ms 5552 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
8 Correct 606 ms 5748 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
9 Correct 606 ms 5564 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
10 Correct 604 ms 5448 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1