Editorial for TLE '16 Contest 7 P3 - NOR - Olympiads Online Judge

Editorial for TLE '16 Contest 7 P3 - NOR

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: d

It is not necessary to use a segment tree or a sparse table to solve this problem. These approaches are overkill and run quite slowly. Binary search is also not necessary, and it increases execution time.

The first observation is that $\text{anything} \operatorname{NOR} 1 = 0$ $anything NOR 1 = 0$ , where $\text{anything}$ $anything$ can be any expression. In particular, if $A_y = 1$ $A_{y} = 1$ , then the answer to the query $x\ y$ $x y$ is always $0$ $0$ .

To solve a query, it is only necessary to get the largest $k$ $k$ that satisfies both $k \le y$ $k \leq y$ and $A_k=1$ $A_{k} = 1$ . In case $A_1 \dots A_y$ $A_{1} \dots A_{y}$ are all 0's, let $k=0$ $k = 0$ . This information can be preprocessed and stored in an array in $\mathcal{O}(N)$ $O (N)$ time (linear time). Now there are $3$ $3$ cases to consider:

$k<x$ $k < x$ : In this case, all integers are equal to $0$ $0$ .
$k=x$ $k = x$ : In this case, only the first integer is equal to $1$ $1$ . The rest are equal to $0$ $0$ .
$k>x$ $k > x$ : In this case, $(A_x \operatorname{NOR} A_{x+1} \operatorname{NOR} \dots \operatorname{NOR} A_k) = 0$ $(A_{x} NOR A_{x + 1} NOR \dots NOR A_{k}) = 0$ , because $A_k=1$ $A_{k} = 1$ and $\text{anything} \operatorname{NOR} 1 = 0$ $anything NOR 1 = 0$ .

A query can be solved in $\mathcal{O}(1)$ $O (1)$ (constant time). Make sure to print the correct answer for each case.

Time Complexity: $\mathcal{O}(N+Q)$ $O (N + Q)$

Comments

There are no comments at the moment.