시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 2625 | 660 | 489 | 27.334% |
길이가 동일한 수열 $X=(x_0, x_1, \cdots, x_{n-1})$와 $Y=(y_0, y_1, \cdots, y_{n-1})$가 있다.
이 두 수열의 각 원소는 음이 아닌 정수이다. 다음은 $n=5$인 경우의 한 예이다.
\[X=(1,0,0,0,1)\]
\[Y=(0,5,2,0,1)\]
임의의 정수 $t$가 주어졌을 때 $XCorr(t)$는 다음과 같이 정의된다.
\[XCorr(t)=\displaystyle\sum_{i=0}^{n-1}{x_iy_{i+t}}\]
($i<0$이거나 $i\geq n$이면 $x_i=y_i=0$으로 간주한다.)
예를 들어 $t$가 $0, 1, -1$일 때, $XCorr(t)$값은 다음과 같이 계산된다.
\[XCorr(0) = x_0y_0 + x_1y_1 + \dots + x_{n-1}y_{n-1}\]
\[XCorr(1) = x_0y_1 + x_1y_2 + \dots + x_{n-1}y_n\]
회색 칸에 들어있는 부분은 계산결과에 영향을 주지 않음에 주의하라. $y_0$는 계산식에 포함되지 않고, $x_{n-1}$은 곱해지는 $y_n=0$ 이므로 계산 결과에 영향을 주지 않는다. 따라서 예시 수열 $X$와 $Y$에서 $XCorr(1)$은 다음과 같이 계산할 수 있다.
\[1\times5+0\times2+0\times0+0\times1=5\]
\[XCorr(-1) = x_0y_{-1} + x_1y_0 + \dots + x_{n-1}y_{n-2}\]
임의의 $t$값의 범위 $(a \le t \le b)$에 대해 $XCorr(t)$를 모두 구해서 더한 값 $S(a,b)$는 다음과 같이 정의된다.
\[S(a,b)=\displaystyle\sum_{a \le t \le b}{XCorr(t)}\]
수열 $X$,$Y$와 $t$의 범위 $a$, $b$가 주어졌을 때 $S(a,b)$를 구하는 프로그램을 작성하시오.
표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 수열 $X$에서 0이 아닌 정수의 개수 $N$이 주어진다.(수열의 길이 $n$이 아님). 다음 $N$개의 줄에는 수열 $X$의 각 양의 정수 $x_i$에 대해 인덱스 $i$ 와 $x_i$ 값이 인덱스의 오름차순으로 주어진다. 다음 줄부터는 수열 $Y$가 $X$와 동일한 방식으로 주어진다. ($Y$에서 0이 아닌 정수의 개수 $M$이 주어지고 다음 $M$개의 줄에는 수열 $Y$의 각 양의 정수 $y_i$에 대해 인덱스 $i$와 $y_i$ 값이 인덱스의 오름차순으로 주어진다.) 다음 줄에는 $t$의 범위의 최솟값인 정수 $a$가 주어지고, 그 다음 줄에는 $t$의 범위의 최댓값인 정수 $b$ ($a \le b$)가 주어진다.
표준 출력으로 $S(a,b)=\displaystyle\sum_{a \leq t \leq b}{XCorr(t)}$ 값을 정수로 출력하라.
모든 서브태스크에서 입력으로 주는 $x_i, y_i$는 $1 \leq x_i, y_i \leq 3,000$이다.
$ 1 \le N, M \le 3,000, 1 \le n \le 3,000, -3,000 \le a \le b \le 3,000$ 이다.
$1 \le N, M \le 3 \times 10^5, 1 \le n \le 3 \times 10^5, -3 \times 10^5 \le a \le b \le 3 \times 10^5$ 이다.
$1 \le N, M \le 3 \times 10^5, 1 \le n \le 10^9, -10^9 \le a \le b \le 10^9$이다.
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