DMOPC '15 Contest 4 P4 - Great Sequence

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.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
    pblpbl  commented on Nov. 7, 2019, 11:06 a.m. edit 3

    Anyone know why I am getting a null pointer exception? edit: nvm im bad

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

    What is wrong with my program? Second subtask passes

    • 1
      r3mark  commented on Jan. 12, 2016, 7:46 p.m.

      The problem is specifically asking for the subsequence starting from the xth integer to the yth integer (I guess the statement is incorrect, it should say "from the xth integer to the yth integer"). For example, if the sequence were 5, 6, 1, 2, 4, 2, 2 and xi=2 and yi=5, the subsequence would then be 6, 1, 2, 4.

      • 0
        bobhob314  commented on Jan. 12, 2016, 7:52 p.m. edit 2

        ok good, i was scared for a sec there, thx

  • 4
    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.

  • -9
    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.