DMOPC '15 Contest 4 P4 - Great Sequence

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem type

Luke (perhaps Skywalker) is a passionate computer science student. He receives as homework the following task:

Given a sequence of N integers, determine if the subsequence from x to y inclusive is a Great Sequence. A Great Sequence is a sequence that whose sum is strictly greater than K.

Luke thought this is too easy, so he has thought up a new challenge: he'd like to know if a subsequence is an Amazing Sequence. An Amazing Sequence is a Great Sequence in which the integers a and b appear. Given his original sequence, he'd like to answer Q queries, determining if a subsequence is an Amazing Sequence.


For all subtasks, -10^9 \le K \le 10^9 and -1\,000 \le a_i, b_i \le 1\,000 and 1 \le x_i \le y_i \le N.

Subtask 1 [30%]

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

Subtask 2 [70%]

2 \le N \le 10^5
1 \le Q \le 10^5

Input Specification

The first line of input will contain the space-separated integers N, K and Q. The second line of input will contain N space-separated integers representing the sequence. For the last Q lines, line i will contain query i in the format a_i, b_i, x_i and y_i.

Output Specification

For each query, print Yes if the subsequence is an Amazing Sequence, No otherwise.

Sample Input

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

Sample Output



  • 0
    Josh  commented on Nov. 4, 2018, 12:56 a.m.

    What is wrong with my program? Second subtask passes

  • 2
    garmel  commented on Jan. 12, 2016, 2:20 p.m.

    hi everybody, what does mean |R?

    • 3
      Xyene  commented on Jan. 12, 2016, 2:25 p.m.

      IR means Invalid Return: your program exited with a non-zero error code. You can hover over a status code to see a more detailed description.

  • -6
    mightymercado  commented on Jan. 12, 2016, 1:17 p.m. edited

    This comment is hidden due to too much negative feedback. Click here to view it.