oj.uz

Submission #321639

# Submission time Handle Problem Language Result Execution time Memory
321639 2020-11-13T00:45:02 Z peuch Secret (JOI14_secret) C++17
100 / 100
 517 ms 9788 KB 
#include "secret.h"
#include<bits/stdc++.h>

const int MAXN = 1010;

int n;
long long value[MAXN][MAXN];
long long v[MAXN];

void dc(int ini, int fim){
	if(ini == fim) {
		value[ini][ini] = v[ini];
		return;
	}
	int mid = (ini + fim) / 2;

	dc(ini, mid);
	dc(mid + 1, fim);

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

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

long long getVal(int ini, int fim, int l, int r){
	if(ini == fim) return value[ini][ini];
	int mid = (ini + fim) / 2;
	if(l <= mid && r > mid)
		return Secret(value[l][mid], value[mid + 1][r]);
	if(r <= mid)
		return getVal(ini, mid, l, r);
	return getVal(mid + 1, fim, l, r);
}

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

int Query(int L, int R) {
	if(L == R) return v[L];
	return getVal(0, n - 1, L, R);
}

// g++ -o secret -O2 grader.cpp secret.cpp

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 4844 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 144 ms 4844 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 146 ms 4972 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 511 ms 9664 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 512 ms 9580 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 517 ms 9580 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 510 ms 9708 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 511 ms 9708 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 510 ms 9708 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 509 ms 9788 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1