XCorr > 문제은행



문제은행

3235 : XCorr

제한시간: 1Sec    메모리제한: 128mb
해결횟수: 20회    시도횟수: 74회   



길이가 동일한 수열 X = (x0, x1, …, xn-1)와 Y = (y0, y1, …, yn-1)가 있다.

이 두 수열의 각 원소는 음이 아닌 정수이다.

다음은 n=5인 경우의 한 예이다.

 

X = (1, 0, 0, 0, 1)

Y = (0, 5, 2, 0, 1)

 

임의의 정수 t가 주어졌을 때 XCorr(t)는 다음과 같이 정의된다.

 

 5321aa34e52c55673fbbb84628c752ab_1532755 

 

(i < 0 이거나 i ≥ n 이면 xi = yi = 0으로 간주한다.)

 

예를 들어 t가 0, 1, -1일 때, XCorr(t)값은 다음과 같이 계산된다.

 

5321aa34e52c55673fbbb84628c752ab_1532756
 

회색 칸에 들어있는 부분은 계산결과에 영향을 주지 않음에 유의하라. 

y0는 계산식에 포함되지 않고 xn-1은 곱해지는 yn = 0이므로 계산 결과에 영향을 주지 않는다.

따라서 예시 수열 X와 Y에서 XCorr(1)은 다음과 같이 계산할 수 있다.

 

5321aa34e52c55673fbbb84628c752ab_1532756
 

임의의 t값의 범위( a ≤ t ≤ b)에 대해 XCorr(t)를 모두 구해서 더한 값 S(a, b)는 다음과 같이 정의된다.

 

5321aa34e52c55673fbbb84628c752ab_1532756 

 

수열 X, Y와 t의 범위 a, b가 주어졌을 때 S(a, b)를 구하는 프로그램을 작성하시오.

 

소스파일의 이름은 XCorr.c 또는 XCorr.cpp를 권장하지만, 서버에 제출하는 데는 다른 이름도 상관없다.

 


표준 입력으로 다음 정보가 주어진다.
첫 번째 줄에는 수열 X에서 0 이 아닌 정수의 개수 N이 주어진다.(수열 X의 길이 n이 아님).
다음 N개의 줄에는 수열 X의 각 양의 정수 값 xi에 대해 인덱스 i와 xi값이 인덱스의 오름차순으로 주어진다.
다음 줄부터는 수열 Y가 X와 동일한 방식으로 주어진다.
(Y에서 0 이 아닌 정수의 개수 M이 주어지고 다음 M개의 줄에는 수열 Y의 각 양의 정수 값 yi에 대해
인덱스 i와 yi값이 인덱스의 오름차순으로 주어진다.)
다음 줄에는 t의 범위의 최솟값인 정수 a가 주어지고 그 다음 줄에는 t의 범위의 최댓값인 정수 b(a <= b)가 주어진다.


표준 출력으로 값을 정수로 출력하라.

[부분문제의 제약 조건]
* 부분문제 1: 전체 100점 중 19점에 해당하며 
  1 ≤ N, M ≤ 3,000,  1 ≤ n ≤ 3,000,  -3,000 ≤ a ≤ b ≤ 3,000이다.
* 부분문제 2: 전체 100점 중 42점에 해당하며 
  1 ≤ N, M ≤ 3 × 105,  1 ≤ n ≤ 3 × 105​,  -3 × 10​5​ ≤ a ≤ b ≤ 3 × 10​5​이다. 
* 부분문제 3: 전체 100점 중 39점에 해당하며 
  1 ≤ N, M ≤ 3 × 105,  1 ≤ n ≤ 109​,  -109​ ≤ a ≤ b ≤ 109​ ​​이다.

[Copy]
3
0 1
1 1
2 1
3
0 1
1 2
2 3
-1
1
[Copy]
14


[Copy]
3
0 1
4 4
9 5
3
1 3
2 7
10 7
-2
2
[Copy]
73






HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.