DMOPC '15 Contest 4 P4 - Great Sequence - DMOJ: Modern Online Judge

DMOPC '15 Contest 4 P4 - Great Sequence

Points: 10 (partial)

Time limit: 0.2s

Java 1.0s

Python 1.0s

Memory limit: 64M

Authors:

WallE256, ionutpop118

Problem type

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

Given a sequence of $N$ ~N~ integers, determine if the subsequence from $x$ ~x~ to $y$ ~y~ inclusive is a Great Sequence. A Great Sequence is a sequence whose sum is strictly greater than $K$ ~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$ ~a~ and $b$ ~b~ appear. Given his original sequence, he'd like to answer $Q$ ~Q~ queries, determining if a subsequence is an Amazing Sequence.

Constraints

For all subtasks:

$-10^9 \le K \le 10^9$ ~-10^9 \le K \le 10^9~

$-1\,000 \le a_i, b_i \le 1\,000$ ~-1\,000 \le a_i, b_i \le 1\,000~

$1 \le x_i \le y_i \le N$ ~1 \le x_i \le y_i \le N~

Subtask 1 [30%]

$N \le 1\,000$ ~N \le 1\,000~

$Q \le 1\,000$ ~Q \le 1\,000~

Subtask 2 [70%]

$2 \le N \le 10^5$ ~2 \le N \le 10^5~

$1 \le Q \le 10^5$ ~1 \le Q \le 10^5~

Input Specification

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

Output Specification

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

Sample Input

Sample Output

Yes
Yes
No

Comments

2

Kirito commented on Dec. 20, 2022, 5:39 a.m.

Dropped time limit to 0.2s to kill vectorized cheese.

1

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

What is wrong with my program? Second subtask passes