oj.uz

Submission #466474

# Submission time Handle Problem Language Result Execution time Memory
466474 2021-08-19T12:20:16 Z koioi.org-dennisstar Secret (JOI14_secret) C++17
100 / 100
 539 ms 8416 KB 
#include "secret.h"
#include <bits/stdc++.h>

using namespace std;

int n;
vector<vector<int>> ar;

void init(int s, int e) {
	if (s==e) return ;
	int m=(s+e)/2;
	for (int i=m; i>=s; i--) if (ar[i][m]==-1) ar[i][m]=Secret(ar[i][i], ar[i+1][m]);
	for (int i=m+1; i<=e; i++) if (ar[m+1][i]==-1) ar[m+1][i]=Secret(ar[m+1][i-1], ar[i][i]);
	init(s, m); init(m+1, e);
}

void Init(int n, int a[]) {
	::n=n;
	ar.resize(n, vector<int>(n, -1));
	for (int i=0; i<n; i++) ar[i][i]=a[i];
	init(0, n-1);
}

int Query(int l, int r) {
	int s=0, e=n-1;
	while (1) {
		int m=(s+e)/2;
		if (l<=m&&m<=r) {
			if (m==r) return ar[l][m];
			return Secret(ar[l][m], ar[m+1][r]);
		}
		if (m<l) s=m+1;
		else e=m;
	}
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 3400 KB Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1
2 Correct 147 ms 3396 KB Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1
3 Correct 146 ms 3500 KB Output is correct - number of calls to Secret by Init = 3101, maximum number of calls to Secret by Query = 1
4 Correct 526 ms 8416 KB Output is correct - number of calls to Secret by Init = 6989, maximum number of calls to Secret by Query = 1
5 Correct 539 ms 8260 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
6 Correct 520 ms 8284 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
7 Correct 529 ms 8252 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
8 Correct 518 ms 8228 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
9 Correct 535 ms 8400 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
10 Correct 538 ms 8352 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1