제출 #1087964

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1087964		4QT0R	비밀 (JOI14_secret)	C++17	100 / 100	331 ms	5712 KiB

secret

#include <bits/stdc++.h>
#include "secret.h"
using namespace std;

map<pair<int,int>,int> mp;
int mySecret(int X, int Y){
	if (!mp.count({X,Y}))mp[{X,Y}]=Secret(X,Y);
	return mp[{X,Y}];
}

vector<int> lft[1003];
vector<int> rght[1003];
int wej[1003];
int n;

void build(int l, int p){
	if (l==p)return;
	int md=(l+p)/2;
	lft[md].push_back(wej[md]);
	for (int i = md-1; i>=l; i--){
		lft[md].push_back(mySecret(wej[i],lft[md].back()));
	}
	rght[md+1].push_back(wej[md+1]);
	for (int i = md+2; i<=p; i++){
		rght[md+1].push_back(mySecret(rght[md+1].back(),wej[i]));
	}
	build(l,md);
	build(md+1,p);
}

void Init(int N, int A[]){
	for (int i = 0; i<N; i++)wej[i]=A[i];
	n=N;
	build(0,N-1);
}

int find(int l, int p){
	int a=0,b=n-1,md=(a+b)/2;
	while(l>md || p<=md){
		if (l>md)a=md+1;
		else b=md;
		md=(a+b)/2;
	}
	return md;
}

int Query(int l, int p){
	if (l==p)return wej[l];
	int mid=find(l,p);
	return mySecret(lft[mid][mid-l],rght[mid+1][p-mid-1]);
}

• Subtask 1: 100 / 100