oj.uz

Submission #50269

# Submission time Handle Problem Language Result Execution time Memory
50269 2018-06-08T22:36:54 Z MatheusLealV Secret (JOI14_secret) C++17
100 / 100
 706 ms 13748 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 9976 KB Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1
2 Correct 188 ms 10224 KB Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1
3 Correct 188 ms 10408 KB Output is correct - number of calls to Secret by Init = 3101, maximum number of calls to Secret by Query = 1
4 Correct 617 ms 13012 KB Output is correct - number of calls to Secret by Init = 6989, maximum number of calls to Secret by Query = 1
5 Correct 616 ms 13176 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
6 Correct 627 ms 13176 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
7 Correct 626 ms 13488 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
8 Correct 624 ms 13544 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
9 Correct 706 ms 13748 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
10 Correct 660 ms 13748 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1