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} \leq K \leq 10^{9}$

$-1\,000 \le a_i, b_i \le 1\,000$ $- 1 000 \leq a_{i}, b_{i} \leq 1 000$

$1 \le x_i \le y_i \le N$ $1 \leq x_{i} \leq y_{i} \leq N$

Subtask 1 [30%]

$N \le 1\,000$ $N \leq 1 000$

$Q \le 1\,000$ $Q \leq 1 000$

Subtask 2 [70%]

$2 \le N \le 10^5$ $2 \leq N \leq 10^{5}$

$1 \le Q \le 10^5$ $1 \leq Q \leq 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

Copy

Sample Output

Copy

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