oj.uz

Submission #321493

# Submission time Handle Problem Language Result Execution time Memory
321493 2020-11-12T14:17:39 Z Lawliet Secret (JOI14_secret) C++17
100 / 100
 514 ms 8428 KB 
#include "secret.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1010;

int n;

int v[MAXN];
int value[MAXN][MAXN];

int getBreak(int l, int r, int lQuery, int rQuery)
{
	int mid = ( l + r )/2;

	if( lQuery <= mid && mid + 1 <= rQuery ) return mid;

	if( rQuery <= mid ) return getBreak( l , mid , lQuery , rQuery );
	return getBreak( mid + 1 , r , lQuery , rQuery );
}

void DivAndConquer(int l, int r)
{
	if( l == r ) return;

	int mid = ( l + r )/2;

	DivAndConquer( l , mid );
	DivAndConquer( mid + 1 , r );

	for(int t = mid - 1 ; t >= l ; t--)
		value[t][mid] = Secret( v[t] , value[t + 1][mid] );

	for(int t = mid + 2 ; t <= r ; t++)
		value[mid + 1][t] = Secret( value[mid + 1][t - 1] , v[t] );
}

void Init(int N, int A[]) 
{
	n = N;

	for(int i = 0 ; i < n ; i++)
		v[i] = A[i], value[i][i] = A[i];

	DivAndConquer( 0 , n - 1 );
}

int Query(int L, int R)
{
	if( L == R ) return v[L];

	int t = getBreak( 0 , n - 1 , L , R );
	return Secret( value[L][t] , value[t + 1][R] );
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 4460 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 143 ms 4460 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 143 ms 4460 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 509 ms 8428 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 507 ms 8300 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 507 ms 8300 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 514 ms 8428 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 506 ms 8428 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 507 ms 8300 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 508 ms 8300 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1