oj.uz

Submission #1087964

# Submission time Handle Problem Language Result Execution time Memory
1087964 2024-09-13T15:48:13 Z 4QT0R Secret (JOI14_secret) C++17
100 / 100
 331 ms 5712 KB 
#include <bits/stdc++.h>
#include "secret.h"
using namespace std;

map<pair<int,int>,int> mp;
int mySecret(int X, int Y){
	if (!mp.count({X,Y}))mp[{X,Y}]=Secret(X,Y);
	return mp[{X,Y}];
}

vector<int> lft[1003];
vector<int> rght[1003];
int wej[1003];
int n;

void build(int l, int p){
	if (l==p)return;
	int md=(l+p)/2;
	lft[md].push_back(wej[md]);
	for (int i = md-1; i>=l; i--){
		lft[md].push_back(mySecret(wej[i],lft[md].back()));
	}
	rght[md+1].push_back(wej[md+1]);
	for (int i = md+2; i<=p; i++){
		rght[md+1].push_back(mySecret(rght[md+1].back(),wej[i]));
	}
	build(l,md);
	build(md+1,p);
}

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

int find(int l, int p){
	int a=0,b=n-1,md=(a+b)/2;
	while(l>md || p<=md){
		if (l>md)a=md+1;
		else b=md;
		md=(a+b)/2;
	}
	return md;
}

int Query(int l, int p){
	if (l==p)return wej[l];
	int mid=find(l,p);
	return mySecret(lft[mid][mid-l],rght[mid+1][p-mid-1]);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 3416 KB Output is correct - number of calls to Secret by Init = 3324, maximum number of calls to Secret by Query = 1
2 Correct 90 ms 3404 KB Output is correct - number of calls to Secret by Init = 3332, maximum number of calls to Secret by Query = 1
3 Correct 90 ms 3408 KB Output is correct - number of calls to Secret by Init = 3341, maximum number of calls to Secret by Query = 1
4 Correct 316 ms 5696 KB Output is correct - number of calls to Secret by Init = 7483, maximum number of calls to Secret by Query = 1
5 Correct 311 ms 5712 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
6 Correct 331 ms 5704 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
7 Correct 316 ms 5712 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
8 Correct 318 ms 5712 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
9 Correct 324 ms 5700 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1
10 Correct 324 ms 5540 KB Output is correct - number of calls to Secret by Init = 7491, maximum number of calls to Secret by Query = 1