Universal Cup Judging System

Universal Cup

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

Masz możliwość tworzenia robotów o wysokości należącej do przedziału $[0, d]$. Aby je przetestować, zbudowałeś tor o długości $n$ zawierający pewne przeszkody. Opis przeszkód jest podany jako tablica $a$. Jeśli $a_i = 0$, to na $i$-tej pozycji nie ma przeszkody, a w przeciwnym razie znajduje się tam przeszkoda o wysokości $a_i > 0$.

Aby przetestować robota, wybierasz przedział $[l, r]$ i przeprowadzasz go przez wszystkie przeszkody zawarte w tym przedziale. Gdy robot napotyka przeszkodę o wartości $a_i > 0$, zachodzi jedna z dwóch możliwości:

  • Jeśli aktualna wysokość robota $h$ jest mniejsza niż $a_i$, to nic się nie dzieje, ponieważ robot jest zbyt niski, aby dosięgnąć przeszkody.
  • Jeśli aktualna wysokość robota $h$ wynosi co najmniej $a_i$, to nowa wysokość zmienia się na $h' = h - a_i$.

Teraz musisz odpowiedzieć na $q$ zapytań. Dla każdego z $q$ przedziałów $[l_i, r_i]$ musisz podać maksymalną możliwą wysokość, z jaką robot może zakończyć bieg po pokonaniu przeszkód w tym przedziale, jeśli wysokość początkowa została wybrana z przedziału $[0, d]$.

Wejście

Pierwszy wiersz zawiera liczby całkowite $n, q, d$ ($1 \le n, q \le 3 \cdot 10^5, 1 \le d \le 10^9$) — długość tablicy oraz liczbę zapytań.

Drugi wiersz zawiera $n$ liczb całkowitych $a_i$ ($0 \le a_i \le 10^9$) — opis tablicy.

Kolejne $q$ wierszy zawiera pary liczb całkowitych $[l_i, r_i]$ ($1 \le l_i \le r_i \le n$) — opis zapytań.

Wyjście

Wypisz $q$ liczb całkowitych — odpowiedzi na zapytania.

Przykład

Wejście 1

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

Wyjście 1

2
2
3

Wejście 2

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

Wyjście 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.