CCO '22 P1 - Alternating Heights

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 2.0s
Memory limit: 1G

Problem type
Canadian Computing Olympiad: 2022 Day 1, Problem 1

Troy is planning to take a group photo of the students at CCO and has asked you for help.

There are K students, numbered from 1 to K. Troy has forgotten the students' heights but remembers that no two students have the same height.

Troy has prepared a sequence A_1, A_2, \dots, A_N representing the order of students in the group photo, from left to right. It is possible for a student to appear multiple times in A. You aren't sure how this group photo would be taken, but you're unwilling to assume that Troy made a mistake.

Troy will ask you Q queries of the form x y, which is a compact way of asking "Given the sequence of students, A_x, A_{x+1}, \dots, A_y, can their heights form an alternating sequence?" More precisely, we denote the height of the i^\text{th} student as h[i]. If there exists an assignment of heights h[1], h[2], \dots, h[K] such that h[A_x] > h[A_{x+1}] < h[A_{x+2}] > h[A_{x+3}] < \dots h[A_y], answer YES; otherwise, answer NO.

Note that each of the Q queries will be independent: that is, the assignment of heights for query i is independent of the assignment of heights for query j so long as i \ne j.

Input Specification

The first line of input will contain three space-separated integers N, K, and Q.

The second line of input will contain the array A_1, A_2, \dots, A_N (1 \le A_i \le K).

The next Q lines will each contain a query of the form of two space-separated integers x and y (1 \le x < y \le N).

Marks AwardedBounds on NBounds on KBounds on Q
4 marks2 \le N \le 3\,000K = 21 \le Q \le 10^6
6 marks2 \le N \le 5002 \le K \le \min(N, 5)1 \le Q \le 10^6
7 marks2 \le N \le 3\,0002 \le K \le N1 \le Q \le 2\,000
8 marks2 \le N \le 3\,0002 \le K \le N1 \le Q \le 10^6

Output Specification

Output Q lines. On the i^\text{th} line, output the answer to Troy's i^\text{th} query. Note that the answer is either YES or NO.

Sample Input

6 3 3
1 1 2 3 1 2
1 2
2 5
2 6

Output for Sample Input


Explanation of Output for Sample Input

For the first query, we will never have h[1] > h[1], so the answer is no.

For the second query, one solution to h[1] > h[2] < h[3] > h[1] is h[1] = 160cm, h[2] = 140cm, h[3] = 180cm. Another solution could be h[1] = 1.55m, h[2] = 1.473m, h[3] = 1.81m.

For the third query, we cannot have both h[1] > h[2] and h[1] < h[2].


There are no comments at the moment.