oj.uz

Submission #94805

# Submission time Handle Problem Language Result Execution time Memory
94805 2019-01-24T06:09:57 Z Retro3014 Secret (JOI14_secret) C++17
100 / 100
 493 ms 9392 KB 
#include "secret.h"
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <iostream>

using namespace std;

#define MAX_N 1000

vector<int> v;
int n;
int dp[MAX_N+1][MAX_N+1];
bool vst[MAX_N+1][MAX_N+1];

void init(int x, int y){
	if(x==y)	{
		return;
	}
	if(x==y-1){
		return;
	}
	int m = (x+y)/2;
	dp[m][m] = v[m];
	dp[m+1][m+1] = v[m+1];
	for(int i=m-1; i>=x; i--)	{
		if(!vst[i][m]){
			dp[i][m] = Secret(v[i], dp[i+1][m]);
			vst[i][m] = true;
		}
	}
	for(int j=m+2; j<=y; j++){
		if(!vst[m+1][j]){
			dp[m+1][j] = Secret(dp[m+1][j-1], v[j]);
			vst[m+1][j] = true;
		}
	}
	init(x, m);
	init(m+1, y);
}


void Init(int N, int A[]) {n = N;
	for(int i=0; i<N; i++){
		v.push_back(A[i]);
	}
	init(0, N-1);
}

int Query(int L, int R) {
	if(L==R){
		return v[L];
	}
	if(L==R-1){
		return Secret(v[L], v[R]);
	}
	int s = 0, e = n-1, m;
	while(1){
		m = (s+e)/2;
		if(L<=m && R>m){
			return Secret(dp[L][m], dp[m+1][R]);
		}
		if(R<=m){
			e = m;
		}else{
			s = m+1;
		}
	}
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 4984 KB Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1
2 Correct 141 ms 5044 KB Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1
3 Correct 141 ms 4912 KB Output is correct - number of calls to Secret by Init = 3101, maximum number of calls to Secret by Query = 1
4 Correct 493 ms 9392 KB Output is correct - number of calls to Secret by Init = 6989, maximum number of calls to Secret by Query = 1
5 Correct 480 ms 9256 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
6 Correct 480 ms 9344 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
7 Correct 485 ms 9328 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
8 Correct 487 ms 9296 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
9 Correct 485 ms 9180 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
10 Correct 483 ms 9336 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1