Universal Cup Judging System

Universal Cup

時間限制: 1.0 s 記憶體限制: 256 MB 總分: 100 可 Hack ✓
统计

Sie haben die Fähigkeit, Roboter mit einer Höhe im Bereich $[0, d]$ zu bauen. Um sie zu testen, haben Sie eine Strecke der Länge $n$ mit einigen Hindernissen errichtet. Die Beschreibung der Hindernisse ist als Array $a$ gegeben. Wenn $a_i = 0$ ist, befindet sich an der $i$-ten Position kein Hindernis, andernfalls gibt es dort ein Hindernis der Höhe $a_i > 0$.

Um Ihren Roboter zu testen, wählen Sie ein Segment $[l, r]$ aus und lassen ihn alle in diesem Segment enthaltenen Hindernisse durchlaufen. Wenn der Roboter auf ein Hindernis mit dem Wert $a_i > 0$ trifft, tritt eine der beiden folgenden Möglichkeiten ein:

  • Wenn die aktuelle Höhe $h$ des Roboters kleiner als $a_i$ ist, passiert nichts, da der Roboter zu klein ist, um das Hindernis zu berühren.
  • Wenn die aktuelle Höhe $h$ des Roboters mindestens $a_i$ beträgt, ändert sich die neue Höhe zu $h' = h - a_i$.

Nun müssen Sie $q$ Anfragen beantworten. Für jedes der $q$ Segmente $[l_i, r_i]$ sollen Sie die größtmögliche Endhöhe bestimmen, die der Roboter nach dem Durchlaufen der Hindernisse im Segment haben kann, wenn seine Anfangshöhe aus dem Intervall $[0, d]$ gewählt wurde.

Eingabe

Die erste Zeile enthält die ganzen Zahlen $n, q, d$ ($1 \le n, q \le 3 \cdot 10^5, 1 \le d \le 10^9$) — die Länge des Arrays und die Anzahl der Anfragen.

Die zweite Zeile enthält $n$ ganze Zahlen $a_i$ ($0 \le a_i \le 10^9$) — die Beschreibung des Arrays.

Die nächsten $q$ Zeilen enthalten jeweils ein Paar ganzer Zahlen $[l_i, r_i]$ ($1 \le l_i \le r_i \le n$) — die Beschreibung der Anfragen.

Ausgabe

Geben Sie $q$ ganze Zahlen aus — die Antworten auf die Anfragen.

Beispiele

Eingabe 1

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

Ausgabe 1

2
2
3

Eingabe 2

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

Ausgabe 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.