Submission #50269

#	Time	Username	Problem	Language	Result	Execution time	Memory
50269		MatheusLealV	Secret (JOI14_secret)	C++17	100 / 100	706 ms	13748 KiB

secret

#include <bits/stdc++.h>
#define f first
#define s second
#define maxn 1234
#define mid ((a + b)/2)
#include "secret.h"
using namespace std;
typedef pair<int, int> pii;
 
int v[maxn], tree[4*maxn], inutil, n, ans[maxn][maxn], ini[maxn];
 
map<pii, int> dp;
 
int S(int a, int b)
{
	if(dp[pii(a, b)] != 0) return dp[pii(a, b)];
 
	return dp[pii(a, b)] = dp[pii(b, a)] = Secret(a, b);
}
 
void build(int nod, int a, int b)
{
	if(b - a <= 1) return;
 
  for (int i = mid - 1; i >= a; --i)
  		if(ans[i][mid] == -1) ans[i][mid] = S(ans[i][i + 1], ans[i + 1][mid]);
 
  for (int i = mid + 1; i <= b; ++i)
  	    if(ans[mid][i] == -1) ans[mid][i] = S(ans[mid][i - 1], ans[i - 1][i]);
 
	build(2*nod, a, mid), build(2*nod + 1, mid, b);
}
 
int Query(int l, int r)
{
	if(r < l) swap(l, r);
 
	for(int i = l + 1; i <= r; i++)
	{
		if(ans[l][i] != -1 && ans[i][r + 1] != -1) return S(ans[l][i], ans[i][r + 1]);
	}
 
	return ans[l][r + 1];
}
 
void Init(int N, int A[])
{
    n = N;
    
    memset(ans, -1, sizeof ans);
 
	for(int i = 0; i < n; i++) v[i] = A[i], ans[i][i + 1] = v[i];
 
	build(1, 0, n);
}

• Subtask 1: 100 / 100