32262번 - Pyramids 서브태스크다국어언어 제한함수 구현

문제

Everyone knows that Pharaoh Khufu was a great ruler, but many are unaware that he was also a fashion enthusiast. Back in the day, he had $N$ pyramids numbered from 0ドル$ to $N - 1,ドル with pyramid $i$ (0ドル ≤ i < N$) consisting of $A[i]$ stones. He also had the latest catalogue of the most fashionable pyramids of the year. The catalogue consists of $N$ pyramids numbered from 0ドル$ to $N - 1,ドル with pyramid $i$ (0ドル ≤ i < N$) consisting of $B[i]$ stones.

For any $x$ and $y,ドル such that 0ドル ≤ x ≤ y < N,ドル we define a range of pyramids $A[x..y]$ to be a sequence $A[x], A[x + 1], \dots , A[y]$. We also define a range of pyramids $B[x..y]$ analogously.

Every day, Khufu would browse the catalogue and choose two ranges of pyramids $A[L..R]$ and $B[X..Y ]$ where $R - L = Y - X$ (the values of $L,ドル $R,ドル $X$ and $Y$ may be different every day). After that, he would like to know whether it's possible to transform his range $A[L..R]$ to become equal to the catalogue's range $B[X..Y ]$. Transforming a range consists of performing the following step an arbitrary number of times: take one stone from a pyramid within the range and move it to an adjacent pyramid within the range.

Your task is to answer multiple questions of the following form. Given four integers $L,ドル $R,ドル $X,ドル and $Y,ドル determine whether it is possible to transform $A[L..R]$ into $B[X..Y ]$. Note that the number of stones in each pyramid never actually changes, Khufu only wonders if one range could be transformed into the other one.

구현 상세

You should implement the following procedures:

void init(std::vector<int> A, std::vector<int> B)

• $A,ドル $B$: two arrays of length $N,ドル describing the number of stones in Khufu's pyramids and in the catalogue respectively.
• This procedure is called exactly once, before any calls to can_transform.

bool can_transform(int L, int R, int X, int Y)

• $L,ドル $R$: starting and ending indices of Khufu's pyramids range.
• $X,ドル $Y$: starting and ending indices of catalogue's pyramids range.
• This procedure should return true if it's possible to transform $A[L..R]$ into $B[X..Y ]$ and false otherwise.
• This procedure is called exactly $Q$ times, once for each day.

입력

출력

제한

• 1ドル ≤ N ≤ 100,円 000$
• 1ドル ≤ Q ≤ 100,円 000$
• 1ドル ≤ A[i] ≤ 10^9$
• 1ドル ≤ B[i] ≤ 10^9$

In each call to can_transform:

• 0ドル ≤ L ≤ R < N$
• 0ドル ≤ X ≤ Y < N$
• $R - L = Y - X$

예제

Consider the following call:

init([1, 2, 3, 4, 5], [2, 2, 2, 4, 5])

Assume the grader then calls can_transform(0, 2, 0, 2). This call should return whether sequence of pyramids $A[0..2] = [1, 2, 3]$ can be transformed into $B[0..2] = [2, 2, 2]$. This is indeed possible by moving 1ドル$ stone from the last to the first pyramid in the range. Therefore, this call should return true.

Assume the grader then calls can_transform(3, 4, 3, 4). This call should return whether we can transform Khufu's pyramids $A[3..4] = [4, 5]$ to $B[3..4] = [4, 5]$ or not. The pyramids already look alike. Therefore, this call should return true.

Assume the grader then calls can_transform(0, 2, 1, 3). This call should return whether sequence of pyramids $A[0..2] = [1, 2, 3]$ can be transformed into $B[1..3] = [2, 2, 4]$. This is not possible, and thus this call should return false.

서브태스크

힌트

샘플 그레이더

Input format:

N Q
A[0] A[1] ... A[N-1]
B[0] B[1] ... B[N-1]
L[0] R[0] X[0] Y[0]
L[1] R[1] X[1] Y[1]
...
L[Q-1] R[Q-1] X[Q-1] Y[Q-1]

Here, $L[i],ドル $R[i],ドル $X[i],ドル and $Y[i]$ denote the values of $L,ドル $R,ドル $X$ and $Y$ in the $i$-th call to can_transform, respectively.

Output format:

P[0]
P[1]
...
P[Q-1]

Here, $P[i]$ is 1ドル$ if the $i$-th call to can_transform returns true and 0ドル$ otherwise.

첨부

• pyramids.zip