답안 #239194

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
239194	2020-06-14T18:44:31 Z	rqi	비밀 (JOI14_secret)	C++14	100 / 100	526 ms	4472 KB

secret

#include "secret.h"
#include <bits/stdc++.h>
int A[1005];
int val[1005][10];
int N;
void build(int L, int R, int lvl = 0){
	if(L > R) return;
	if(L == R){
		val[L][lvl] = A[L];
		return;
	}
	int M = (L+R)/2;
	val[M][lvl] = A[M];
	for(int i = M-1; i >= L; i--){
		val[i][lvl] = Secret(A[i], val[i+1][lvl]);
	}
	val[M+1][lvl] = A[M+1];
	for(int i = M+2; i <= R; i++){
		val[i][lvl] = Secret(val[i-1][lvl], A[i]);
	}
	build(L, M-1, lvl+1);
	build(M+2, R, lvl+1);
}

int query(int l, int r, int L = 0, int R = N-1, int lvl = 0){
	int M = (L+R)/2;
	if(r <= M-1){
		return query(l, r, L, M-1, lvl+1);
	}
	if(l >= M+2){
		return query(l, r, M+2, R, lvl+1);
	}
	
	if(l >= M+1){
		return val[r][lvl];
	}
	if(r <= M){
		return val[l][lvl];
	}

	return Secret(val[l][lvl], val[r][lvl]);
}




void Init(int _N, int a[]) {

	N = _N;
	for(int i = 0; i < N; i++) A[i] = a[i];
	build(0, N-1);
}

int Query(int L, int R) {
	return query(L, R);
}

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	147 ms	2528 KB	Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1
2	Correct	145 ms	2424 KB	Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1
3	Correct	146 ms	2424 KB	Output is correct - number of calls to Secret by Init = 3100, maximum number of calls to Secret by Query = 1
4	Correct	511 ms	4440 KB	Output is correct - number of calls to Secret by Init = 6988, maximum number of calls to Secret by Query = 1
5	Correct	504 ms	4388 KB	Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
6	Correct	517 ms	4360 KB	Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
7	Correct	507 ms	4472 KB	Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
8	Correct	506 ms	4344 KB	Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
9	Correct	516 ms	4472 KB	Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1
10	Correct	526 ms	4396 KB	Output is correct - number of calls to Secret by Init = 6996, maximum number of calls to Secret by Query = 1