DMPG '15 G6 - Yōkan

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 1.4s
Memory limit: 256M

Problem types
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

One day, Michiru and Makina found a great big Yōkan in Amane's room. This was no ordinary yōkan — it was rod-shaped and very long. Laid out horizontally, you can see that the yōkan is composed of N segments, each segment one of M different flavors (numbered from 1 to M). Since the yōkan is so long, they may not be able to eat all of it. Therefore, they will choose a contiguous subsequence of the yōkan to eat. The girls will only eat pieces of one flavor because eating different flavors together will decrease the overall taste. If the length of the subsequence of the yōkan they choose to eat is L, the girls both want to pick a flavor that has at least \dfrac{L}{3} (real division, not integer division) pieces available for them to eat. They can pick the same flavor, but there must be enough pieces of that flavor for both of them to eat. Michiru and Makina have Q queries. Each query is in the form of l\ r — can the girls choose two (not necessarily different) flavors of yōkan that satisfies the above conditions if they only consider the sub-yōkan from l to r?

Note: Michiru and Makina can eat fractional pieces.

Input Specification

The first line of input will have N and M.
The second line of input will have N integers each between 1 and M (inclusive), the flavors of the pieces of yōkan, from left to right.
The third line of input will have Q, the number of queries.
The next Q lines each contain two integers l and r, the queries.


For all subtasks,
1 \le M \le N
1 \le l \le r \le N

Subtask 1 [20%]

1 \le N, Q \le 100

Subtask 2 [20%]

1 \le N, Q \le 10\,000

Subtask 3 [20%]

1 \le N, Q \le 50\,000
1 \le M \le 10

Subtask 4 [40%]

1 \le N, Q \le 200\,000

Output Specification

For each query, output a single line containing either YES (if the conditions can be satisfied) or NO (if the conditions can't be satisfied).

Sample Input

15 3
1 2 3 2 3 3 2 3 1 1 2 3 2 1 2
1 15
1 2
1 4
7 11
5 6

Sample Output


Explanation of Output for Sample Input

In the first query, we can choose flavors 2 and 3.
In the second query, we can choose flavors 1 and 2.
In the third query, no matter which of single or pair of flavors we choose, there won't be enough for both Michiru and Makina.
In the fourth query, we can choose 1 and 2.
In the fifth query, we can choose the single flavor 3, and give one to both Michiru and Makina (since they only require at least \dfrac{2}{3} = 0.\overline{6} pieces each.


  • 1
    gye_tgm  commented on May 28, 2015, 1:18 p.m.

    Is r-l+1=L?

  • 0
    Egor  commented on May 28, 2015, 12:14 p.m.

    Can girls split piece in half between them?

  • 1
    nullptr  commented on May 28, 2015, 12:06 p.m.

    Can a girl eat 2.5 segments of a given flavour?

    • 1
      FatalEagle  commented on May 28, 2015, 12:29 p.m. edited

      I stand corrected.

      • 1
        nullptr  commented on May 28, 2015, 1:23 p.m.

        I can only get AC when I assume that you can split segments.

        • 1
          gye_tgm  commented on May 28, 2015, 1:27 p.m.

          Thanks for the tip!