All Tracks Data Structures Arrays 1-D Problem

Fixed parities
/

1-D Array, Arrays, Data Structures

Problem
Editorial
Analytics

Alice and Bob are playing a board game. They have \(n \times n\) boards and two arrays \(a\) and \(b\) of length \(n\). The value of each cell in the \(i^{th}\) row and \(j^{th}\) row is \(a[i]+b[j]\). Alice asks \(q\) questions to Bob. In each question, Alice provides two cells \(A\) and \(B\). She asks the following questions to Bob:

Are there any paths from \(A\) to \(B\) that contains the same parity as \(A\) and \(B\).

Note: Bob can move from one cell to 8 neighbor cells in each step.

Input format

  • First line: An integer \(n\) denoting the length of arrays
  • Second line: \(n\) integers with \(a_{i}\) representing array \(a\)
  • Third line: \(n\) integers with \(b_{i}\) representing array \(b\)
  • Fourth line: An integer \(q\)  denoting the number of test cases
  • For each test case:
    • First line: Two integers \(r_{1},c_{1}\) denoting the row and the column of \(A\)
    • Second line: Two integers \(r_{2},c_{2}\)denoting the row and the column of \(B\)

Output format

For each query, if there exists a path (for example, \(C\)) from \(A\) to \(B\) that contains the same parity as \(A\) and \(B\), then print YES. If the parity of A and B are different, then print NO.

Constraints

\(1\le n \le 10^{5}\)

\(0\leq r_i \leq 10^6\)

\(0\leq c_i \leq 10^6\)

\(1\le q \le 10^{5}\)

\(1 \leq r_1, c_1 \leq n\)

\(1 \leq r_2, c_2 \leq n\)

SAMPLE INPUT
3
0 3 1
1 5 3
2
2 1
3 3
3 1
1 3
SAMPLE OUTPUT
YES
NO
Explanation

In the first query, we can move from $$(2, 1)$$ to $$(2, 2)$$ then to $$(3, 3)$$.

In the second query, the parity of two cells is different and therefore there isn't such a way.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?