oj.uz

답안 #329817

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
329817 2020-11-22T17:04:26 Z GioChkhaidze 비밀 (JOI14_secret) C++14
0 / 100
 508 ms 9836 KB 
#include <bits/stdc++.h>
#include "secret.h"

#define ll long long

using namespace std;

const int M=1e3+5;

ll n,a[M],ans[M][M];

void Go(int l,int r) {
	if (r-l<2) return ;
	
	int mid=(l+r)/2;

	// left segment l...mid
 	// right segment mid+1...r

	for (int i=mid-1; i>=l; i--) 
  	ans[i][mid]=Secret(ans[i+1][mid],a[i]);

  for (int i=mid+2; i<=r; i++)
  	ans[mid+1][i]=Secret(ans[mid+1][i-1],a[i]);
  	
  Go(l,mid);
	Go(mid+1,r);	
}

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

int ansL,ansR;

int Get(int l,int r) {
	if (r-l<2) return 0;
	if (!(l<=ansL && ansR<=r)) return 0;
	int mid=(l+r)/2;
	
	if (ansL<=mid && mid+1<=ansR) {
		return Secret(ans[ansL][mid],ans[mid+1][ansR]);
	}

	return Get(l,mid)+Get(mid+1,r);		
}

int Query(int L, int R) {
	if (L==R) return ans[L][R];
	if (R-L==1) return Secret(a[R],a[L]);

	ansL=L,ansR=R;
	return Get(0,n-1);
}

Subtask #1
0.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 137 ms 4844 KB Wrong Answer: Query(113, 206) - expected : 536899947, actual : 538256673.
2 Incorrect 133 ms 4844 KB Wrong Answer: Query(60, 375) - expected : 669221184, actual : 311474560.
3 Incorrect 134 ms 4844 KB Wrong Answer: Query(211, 401) - expected : 674373968, actual : 353554500.
4 Incorrect 493 ms 9836 KB Wrong Answer: Query(90, 497) - expected : 397934825, actual : 343081568.
5 Incorrect 500 ms 9708 KB Wrong Answer: Query(587, 915) - expected : 752404486, actual : 957013316.
6 Incorrect 497 ms 9836 KB Wrong Answer: Query(747, 749) - expected : 244228265, actual : 935077363.
7 Incorrect 500 ms 9836 KB Wrong Answer: Query(84, 976) - expected : 742463504, actual : 675449873.
8 Incorrect 502 ms 9708 KB Wrong Answer: Query(58, 987) - expected : 20022464, actual : 273091792.
9 Incorrect 499 ms 9716 KB Wrong Answer: Query(33, 967) - expected : 676869696, actual : 827853577.
10 Incorrect 508 ms 9836 KB Wrong Answer: Query(116, 961) - expected : 68487362, actual : 337854787.