oj.uz

Submission #525916

# Submission time Handle Problem Language Result Execution time Memory
525916 2022-02-13T08:02:48 Z Nihal_9936 Secret (JOI14_secret) C++14
100 / 100
 455 ms 8212 KB 
#include <bits/stdc++.h>
using namespace std;
#include "secret.h"

int dp[1001][1001];
int n;

void solve(int f, int l, int A[]){
	int mid = (f + l) / 2;
	dp[mid][mid] = A[mid];
	dp[mid + 1][mid + 1] = A[mid + 1];

	for(int i = mid - 1; i >= f; i--){
		dp[mid][i] = Secret(A[i], dp[mid][i + 1]);
	}

	for(int i = mid + 2; i <= l; i++){
		dp[mid + 1][i] = Secret(dp[mid + 1][i - 1], A[i]);
	}

	if(f < mid) solve(f, mid, A);
	if(mid + 1 < l) solve(mid + 1, l, A); 
}


void Init(int N, int A[]) {
	// for(int i = 0; i < 1001; i++){
	// 	for(int j = 0; j < 1001; j++){
	// 		dp[i][j] = -1;
	// 	}
	// }
	n = N;
	solve(0, n - 1, A);
}

int Query(int l, int r){
	int f = 0, ls = n - 1;
	while(true){
		int mid = (f + ls) / 2;
		if(l <= mid and mid < r){
			return Secret(dp[mid][l], dp[mid + 1][r]);
		}
		if(mid == r) return dp[mid][l];

		if(r <= mid){
			ls = mid;
		}else{
			f = mid + 1;
		}
	}
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 4292 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 123 ms 4292 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 123 ms 4360 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 455 ms 8188 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 445 ms 8180 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 433 ms 8144 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 442 ms 8212 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 440 ms 8116 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 442 ms 8120 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 431 ms 8132 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1