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

Du får en array $a$ som består av $n$ positiva heltal. Vissa element i $a$ saknas dock och har ersatts med nollor.

Definiera oscillationen av $a$ på ett segment $[\ell, r]$ som $\max(a_\ell, \dots, a_r) - \min(a_\ell, \dots, a_r)$.

Du får $q$ segment på formen $[\ell_i, r_i]$. Ersätt varje nolla i $a$ med ett positivt heltal för att minimera summan av oscillationerna av $a$ på alla $q$ segment.

Indata

Den första raden innehåller två heltal $n$ och $q$ ($1 \le n, q \le 2 \cdot 10^5$).

Den andra raden innehåller $n$ heltal $a_1, \dots, a_n$ ($0 \le a_i \le 10^9$): elementen i arrayen. Här betyder $a_i = 0$ att det $i$-te elementet saknas.

De följande $q$ raderna beskriver segmenten. Var och en av dem innehåller två heltal $\ell_i$ och $r_i$ ($1 \le \ell_i \le r_i \le n$).

Utdata

Skriv ut ett enda heltal: den minimala summan av oscillationerna av $a$ på alla givna segment.

Exempel

Indata 1

5 2
2 1 0 3 2
1 3
3 5

Utdata 1

2

Indata 2

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

Utdata 2

2

Indata 3

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

Utdata 3

6

Förklaring

I det första exemplet är den enda optimala arrayen $a = [2, 1, 2, 3, 2]$.

I det andra exemplet finns det flera optimala arrayer. Till exempel är $a = [1, 2, 3, 2, 1]$ optimal.

I det tredje exemplet finns det flera optimala arrayer. Till exempel är $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.