oj.uz

Submission #384098

# Submission time Handle Problem Language Result Execution time Memory
384098 2021-03-31T12:44:49 Z ritul_kr_singh Secret (JOI14_secret) C++17
100 / 100
 510 ms 8428 KB 
#include "secret.h"
#include <bits/stdc++.h>
using namespace std;

int b[1000][1000], n;
vector<array<int, 2>> c;

void PreCalc(int lx, int rx){
	if(rx-lx<=2) return;
	int mx = (lx+rx)/2;
	PreCalc(lx, mx);
	PreCalc(mx, rx);

	c.push_back({lx, rx});
}

void Init(int N, int a[]){
	n = N;
	for(int i=0; i<1000; ++i)
		for(int j=0; j<1000; ++j)
			b[i][j] = i-j ? -1 : a[i];
	PreCalc(0, n);
	for(auto z : c){
		int lx = z[0], rx = z[1];
		int mx = (lx+rx)/2;

		for(int i=mx-2; i>=lx; --i)
			b[i][mx-1] = Secret(b[i][i], b[i+1][mx-1]);
		for(int i=mx+1; i<rx; ++i)
			b[mx][i] = Secret(b[mx][i-1], b[i][i]);
	}
}

int Calc(int l, int r, int lx, int rx){
	int mx = (lx+rx)/2;
	if(r<mx) return Calc(l, r, lx, mx);
	if(l>=mx) return Calc(l, r, mx, rx);
	return Secret(b[l][mx-1], b[mx][r]);
}

int Query(int L, int R){
	if(L==R) return b[L][L];
	if(L+1==R) return Secret(b[L][L], b[R][R]);
	return Calc(L, R, 0, n);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 6380 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 6380 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 6380 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 504 ms 8300 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 508 ms 8172 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 509 ms 8428 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 8280 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 505 ms 8300 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 509 ms 8172 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 507 ms 8172 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1