oj.uz

Submission #167196

# Submission time Handle Problem Language Result Execution time Memory
167196 2019-12-06T11:21:36 Z workharder Secret (JOI14_secret) C++14
100 / 100
 632 ms 8412 KB 
#include "secret.h"
#include "bits/stdc++.h"
using namespace std;
const int MAXN=1005;

int arr[MAXN],simpan[MAXN][MAXN],n;

void build(int L,int R){
	if(L==R){
		simpan[L][R]=arr[L];
		return;
	}
	int mid=(L+R)/2;
	int now=arr[mid];
	for(int i=mid-1;i>=L;i--){
		simpan[i][mid]=Secret(arr[i],now);
		now=simpan[i][mid];
	}
	now=arr[mid+1];
	for(int i=mid+2;i<=R;i++){
		simpan[mid+1][i]=Secret(now,arr[i]);
		now=simpan[mid+1][i];
	}
	build(L,mid);
	build(mid+1,R);
}

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

int tanya(int x,int y,int L,int R){
	if(L==R){
		return simpan[L][R];
	}
	int mid=(L+R)/2;
	if(y<=mid){  // masuk kiri semua
		return tanya(x,y,L,mid);
	}
	if(x>=mid+1){
		return tanya(x,y,mid+1,R);
	}
	return Secret(simpan[x][mid],simpan[mid+1][y]);
}

int Query(int L,int R){
	L++;R++;
	return tanya(L,R,1,n);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 4500 KB Output is correct - number of calls to Secret by Init = 3578, maximum number of calls to Secret by Query = 1
2 Correct 176 ms 4600 KB Output is correct - number of calls to Secret by Init = 3586, maximum number of calls to Secret by Query = 1
3 Correct 176 ms 4472 KB Output is correct - number of calls to Secret by Init = 3595, maximum number of calls to Secret by Query = 1
4 Correct 610 ms 8240 KB Output is correct - number of calls to Secret by Init = 7969, maximum number of calls to Secret by Query = 1
5 Correct 605 ms 8312 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
6 Correct 611 ms 8280 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
7 Correct 606 ms 8312 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
8 Correct 632 ms 8344 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
9 Correct 606 ms 8284 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1
10 Correct 612 ms 8412 KB Output is correct - number of calls to Secret by Init = 7978, maximum number of calls to Secret by Query = 1