DMPG '19 S6 - A Strange Array

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 2.5s
Memory limit: 256M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Roger has a strange array consisting of N elements, each of which is either 1 or 2. He also has Q queries, each of the form l r x which means that Roger wants to know whether there exists a subarray [a,b] where l \le a \le b \le r whose sum of elements is exactly x.


In all subtasks
1 \le N, Q \le 1\,000\,000
1 \le l \le r \le N
1 \le x \le 2N
Each element of the array is either 1 or 2.

Subtask 1 [20%]

1 \le N, Q \le 2\,000

Subtask 2 [80%]

No additional constraints.

Input Specification

On the first line, there are two space-separated integers, N and Q, denoting the number of elements in the array and the number of queries.
On the second line, there are N space-separated integers, the elements of the array.
On the next Q lines, there are three space-separated integers, l r x, denoting a query.

Output Specification

Output Q lines, where the i-th line is YES if there exists a subarray satisfying the conditions of Roger's i-th query, or NO otherwise.

Sample Input

7 3
1 2 2 1 1 2 1
2 4 3
1 7 8
2 5 7

Sample Output



There are no comments at the moment.