oj.uz

Submission #156547

# Submission time Handle Problem Language Result Execution time Memory
156547 2019-10-06T12:31:50 Z Saboon Secret (JOI14_secret) C++14
100 / 100
 638 ms 8528 KB 
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1000 + 10;

int a[maxn][maxn];
int h[maxn];

void divide(int L, int R, int nowh = 0){
	if (L + 1 == R)
		return;
	int mid = (L + R) >> 1;
	h[mid] = nowh;
	for (int i = mid; i < R; i++)
		if (a[mid][i] == -1)
			a[mid][i] = Secret(a[mid][i - 1], a[i][i]);
	for (int i = mid - 1; i >= L; i--)
		if (a[i][mid - 1] == -1)
			a[i][mid - 1] = Secret(a[i][i], a[i + 1][mid - 1]);
	divide(L, mid, nowh + 1);
	divide(mid, R, nowh + 1);
}

void Init(int N, int A[]){
	memset(a, -1, sizeof a);
	for (int i = 0; i < N; i++)
		a[i][i] = A[i];
	h[0] = h[N] = N + 1;
	divide(0, N);
}

int Query(int L, int R) {
	int mid = L;
	for (int i = L; i <= R + 1; i++)
		if (h[i] < h[mid])
			mid = i;
	if (mid == L or mid == R + 1)
		return a[L][R];
	return Secret(a[L][mid - 1], a[mid][R]);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 6776 KB Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1
2 Correct 180 ms 6504 KB Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1
3 Correct 187 ms 6520 KB Output is correct - number of calls to Secret by Init = 3101, maximum number of calls to Secret by Query = 1
4 Correct 614 ms 8440 KB Output is correct - number of calls to Secret by Init = 6989, maximum number of calls to Secret by Query = 1
5 Correct 611 ms 8376 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
6 Correct 603 ms 8440 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
7 Correct 638 ms 8484 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
8 Correct 636 ms 8528 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
9 Correct 637 ms 8444 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
10 Correct 634 ms 8424 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1