Universal Cup Judging System

Universal Cup

Límite de tiempo: 5.0 s Límite de memoria: 1024 MB Puntuación total: 100 Dificultad: [mostrar] Hackeable ✓
Estadísticas

Gegeben ist ein Array $a$, das aus $n$ positiven ganzen Zahlen besteht. Allerdings fehlen einige Elemente von $a$, und sie wurden durch Nullen ersetzt.

Definiere die Oszillation von $a$ auf einem Segment $[\ell, r]$ als $\max(a_\ell, \dots, a_r) - \min(a_\ell, \dots, a_r)$.

Gegeben sind $q$ Segmente der Form $[\ell_i, r_i]$. Ersetze jede Null in $a$ durch eine positive ganze Zahl, um die Summe der Oszillationen von $a$ auf allen $q$ Segmenten zu minimieren.

Eingabe

Die erste Zeile enthält zwei ganze Zahlen $n$ und $q$ ($1 \le n, q \le 2 \cdot 10^5$).

Die zweite Zeile enthält $n$ ganze Zahlen $a_1, \dots, a_n$ ($0 \le a_i \le 10^9$): die Elemente des Arrays. Hierbei bedeutet $a_i = 0$, dass das $i$-te Element fehlt.

Die nächsten $q$ Zeilen beschreiben die Segmente. Jede von ihnen enthält zwei ganze Zahlen $\ell_i$ und $r_i$ ($1 \le \ell_i \le r_i \le n$).

Ausgabe

Gib eine einzige ganze Zahl aus: die minimale Summe der Oszillationen von $a$ auf allen gegebenen Segmenten.

Beispiele

Eingabe 1

5 2
2 1 0 3 2
1 3
3 5

Ausgabe 1

2

Eingabe 2

5 3
1 0 3 0 1
1 2
2 4
5 5

Ausgabe 2

2

Eingabe 3

7 4
4 4 0 1 0 3 4
1 3
1 3
3 5
4 7

Ausgabe 3

6

Hinweis

Im ersten Beispiel ist das einzige optimale Array $a = [2, 1, 2, 3, 2]$.

Im zweiten Beispiel gibt es mehrere optimale Arrays. Zum Beispiel ist $a = [1, 2, 3, 2, 1]$ optimal.

Im dritten Beispiel gibt es mehrere optimale Arrays. Zum Beispiel ist $a = [4, 4, 4, 1, 2, 3, 4]$ optimal.

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.