TLE '16 Contest 7 P3 - NOR - DMOJ: Modern Online Judge

TLE '16 Contest 7 P3 - NOR

Points: 10 (partial)

Time limit: 0.75s

Memory limit: 256M

Author:

Problem type

A Venn diagram of

A NOR B

from the Wikimedia Commons.

The only required knowledge is the $\operatorname{NOR}$ $NOR$ operator. All of its possible outputs can be stored concisely in this table.

$a$ $a$	$b$ $b$	$a \operatorname{NOR} b$ $a NOR b$
$0$ $0$	$0$ $0$	$1$ $1$
$0$ $0$	$1$ $1$	$0$ $0$
$1$ $1$	$0$ $0$	$0$ $0$
$1$ $1$	$1$ $1$	$0$ $0$

You are given a sequence $A$ $A$ consisting of $0$ $0$ 's and $1$ $1$ 's. Here, the $i^\text{th}$ $i^{th}$ element of $A$ $A$ is denoted with $A_i$ $A_{i}$ . $A$ $A$ has length $N$ $N$ $(2 \le N \le 10^6)$ $(2 \leq N \leq 10^{6})$ , and is indexed from $1$ $1$ to $N$ $N$ .

There are $Q$ $Q$ $(1 \le Q \le 10^5)$ $(1 \leq Q \leq 10^{5})$ queries, with each query consisting of integers $x$ $x$ and $y$ $y$ $(1 \le x < y \le N)$ $(1 \leq x < y \leq N)$ . For each query, output the value of $(A_x \operatorname{NOR} A_{x+1} \operatorname{NOR} \dots \operatorname{NOR} A_{y-1} \operatorname{NOR} A_y)$ $(A_{x} NOR A_{x + 1} NOR \dots NOR A_{y - 1} NOR A_{y})$ by itself on a line. Because the $\operatorname{NOR}$ $NOR$ operator is not associative, please evaluate the operations from left to right.

Input Specification

The first line contains one integer, $N$ $N$ $(2 \le N \le 10^6)$ $(2 \leq N \leq 10^{6})$ .

The second line contains $N$ $N$ space-separated integers. The $i^\text{th}$ $i^{th}$ integer is $A_i$ $A_{i}$ .

The third line contains one integer, $Q$ $Q$ $(1 \le Q \le 10^5)$ $(1 \leq Q \leq 10^{5})$ .

The following $Q$ $Q$ lines contain two space-separated integers, $x$ $x$ and $y$ $y$ $(1 \le x < y \le N)$ $(1 \leq x < y \leq N)$ .

Subtask	Points	Additional Constraints
1	20	$N=2$ $N = 2$ , $Q=1$ $Q = 1$
2	20	$N \le 2\,000$ $N \leq 2 000$ , $Q \le 2\,000$ $Q \leq 2 000$
3	60	No additional constraints.

Output Specification

For each query, output the result of $(A_x \operatorname{NOR} A_{x+1} \operatorname{NOR} \dots \operatorname{NOR} A_{y-1} \operatorname{NOR} A_y)$ $(A_{x} NOR A_{x + 1} NOR \dots NOR A_{y - 1} NOR A_{y})$ . The operations should be evaluated from left to right.

Sample Input

Copy

6
0 1 1 0 0 1
5
1 2
2 6
3 5
4 5
5 6

Sample Output

Copy

Comments

-4

franklai commented on March 24, 2017, 1:29 p.m.

How come when input is 3 5, and the A string is 0 1 1 0 0 1 the output is 1? It should process 1 0 0 which gives a value of 0 when processed with nor?

1

Paradox commented on March 24, 2017, 1:38 p.m.

$1\text{ NOR }0\text{ NOR }0\ =\ ((1\text{ NOR }0)\text{ NOR }0)\ =\ (0\text{ NOR }0)\ =\ 1$ $1 NOR 0 NOR 0 = ((1 NOR 0) NOR 0) = (0 NOR 0) = 1$