Fixed parities
Tag(s):

## 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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

November Circuits '19

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Graphs
• Basic Programming > Input/Output
• Algorithms > Graphs
• Math > Basic Math
• Algorithms > Dynamic Programming