TLE '16 Contest 7 P3 - NOR

View as PDF

Submit solution


Points: 10 (partial)
Time limit: 0.75s
Memory limit: 256M

Author:
Problem type
A Venn diagram of A \operatorname{NOR} B from the Wikimedia Commons.

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

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

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

There are Q (1 \le Q \le 10^5) queries, with each query consisting of integers x and y (1 \le x < y \le 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) by itself on a line. Because the \operatorname{NOR} operator is not associative, please evaluate the operations from left to right.

Input Specification

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

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

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

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

Subtask Points Additional Constraints
1 20 N=2, Q=1
2 20 N \le 2\,000, Q \le 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). The operations should be evaluated from left to right.

Sample Input

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

Sample Output

0
0
1
1
0

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