oj.uz

답안 #924719

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
924719 2024-02-09T14:47:51 Z Hakiers 비밀 (JOI14_secret) C++17
100 / 100
 393 ms 8528 KB 
#include <bits/stdc++.h>
#include "secret.h"
using namespace std;
constexpr int MAXN = 1e3 + 7;
int interval[MAXN][MAXN];
int input[MAXN];
int n;

void dpc(int l, int r){
	if(r < l) return;
	
	int mid = (l+r)/2;
	//cout << "mid" << mid << " " << l << " " << r << "\n";
	
	for(int i = mid - 1; i >= l; i--){
		interval[mid][i] = Secret(input[i], interval[mid][i+1]);
		//cout << i << " " << mid << " " << interval[mid][i] << "\n";
	}	
	
	
	if(mid+1 < n) interval[mid][mid+1] = input[mid+1];
	for(int i = mid+2; i <= r; i++)
		interval[mid][i] = Secret(interval[mid][i-1], input[i]);
	
	dpc(l, mid-1);
	dpc(mid+1, r);	
}

int dpcQ(int l, int r, int a, int b){
	int mid = (l+r)/2;
	
	if(a <= mid && mid <= b){
		//cout << "mid" << mid << "\n";
		if(b == mid) return interval[mid][a];
		return Secret(interval[mid][a], interval[mid][b]); 
	}
	else if(b < mid)
		return dpcQ(l, mid-1, a, b);
	else return dpcQ(mid+1, r, a, b);	
}


void Init(int N, int A[]) {
  //Secret(0, 1000000000);
  n = N;
  for(int i = 0; i < n; i++){
  	input[i] = A[i];
  	interval[i][i] = A[i];
  }
 
  dpc(0, n-1);
  
}

int Query(int L, int R) {
  	return dpcQ(0, n-1, L, R);
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 6684 KB Output is correct - number of calls to Secret by Init = 3331, maximum number of calls to Secret by Query = 1
2 Correct 117 ms 6740 KB Output is correct - number of calls to Secret by Init = 3339, maximum number of calls to Secret by Query = 1
3 Correct 108 ms 6832 KB Output is correct - number of calls to Secret by Init = 3347, maximum number of calls to Secret by Query = 1
4 Correct 391 ms 8372 KB Output is correct - number of calls to Secret by Init = 7467, maximum number of calls to Secret by Query = 1
5 Correct 392 ms 8288 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
6 Correct 384 ms 8372 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
7 Correct 388 ms 8368 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
8 Correct 388 ms 8528 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
9 Correct 393 ms 8272 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
10 Correct 392 ms 8360 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1