Universal Cup Judging System

Universal Cup

Süre Sınırı: 1.0 s Bellek Sınırı: 256 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

あなたは高さが $[0, d]$ の範囲にあるロボットを作ることができます。それらをテストするために、いくつかの障害物を含む長さ $n$ の直線コースを作りました。障害物の情報は配列 $a$ として与えられます。$a_i = 0$ のとき $i$ 番目の位置に障害物はなく、そうでないとき高さ $a_i > 0$ の障害物があります。

ロボットをテストする際、区間 $[l, r]$ を選び、その区間に含まれるすべての障害物を順番に通過させます。ロボットが値 $a_i > 0$ の障害物に遭遇したとき、次の 2 つのうちいずれかが起こります:

  • ロボットの現在の高さ $h$ が $a_i$ より小さい場合、ロボットは低すぎて障害物に届かないため、何も起こりません。
  • ロボットの現在の高さ $h$ が $a_i$ 以上である場合、新しい高さは $h' = h - a_i$ に変化します。

いま、$q$ 個のクエリに答える必要があります。$q$ 個の区間 $[l_i, r_i]$ のそれぞれについて、初期の高さを区間 $[0, d]$ から選んだとき、区間内の障害物を通過した後にロボットが最終的に持ちうる最大の可能な高さを求めてください。

入力

1 行目には整数 $n, q, d$($1 \le n, q \le 3 \cdot 10^5, 1 \le d \le 10^9$)が与えられます。これらは配列の長さとクエリの数です。

2 行目には $n$ 個の整数 $a_i$($0 \le a_i \le 10^9$)が与えられます。これは配列の説明です。

続く $q$ 行には、整数の組 $[l_i, r_i]$($1 \le l_i \le r_i \le n$)が与えられます。これはクエリの説明です。

出力

$q$ 個の整数を出力してください — 各クエリに対する答えです。

入出力例

入力 1

5 3 5
0 2 6 1 3
5 5
1 5
1 3

出力 1

2
2
3

入力 2

7 5 10
7 6 2 5 0 1 4
1 3
1 7
4 7
2 5
4 6

出力 2

3
2
3
3
4

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#374EditorialOpen题解jianglyView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.