DMOPC '15 Contest 4 P4 - Great Sequence

View as PDF

Submit solution


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

Authors:
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.

Constraints

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

Yes
Yes
No

Comments


  • 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


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


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