KOI 전국 2018 고2- XCorr > 문제은행 : 정보올림피아드&알고리즘



3235 : XCorr

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
10 회   
시도횟수
49 회   

문제

길이가 동일한 수열 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)는 다음과 같이 정의된다.

 

  

 

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

 

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

 


 

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

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

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

 


 

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

 

 

 

수열 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​ ​​이다.


입력 예

3
0 1
1 1
2 1
3
0 1
1 2
2 3
-1
1

출력 예

14

입력 예

3
0 1
4 4
9 5
3
1 3
2 7
10 7
-2
2

출력 예

73


two pointer

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP