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

On vous donne un tableau $a$ composé de $n$ entiers strictement positifs. Cependant, certains éléments de $a$ sont manquants et ont été remplacés par des zéros.

On définit l'oscillation de $a$ sur un segment $[\ell, r]$ comme étant $\max(a_\ell, \dots, a_r) - \min(a_\ell, \dots, a_r)$.

On vous donne $q$ segments de la forme $[\ell_i, r_i]$. Remplacez chaque zéro dans $a$ par un entier strictement positif afin de minimiser la somme des oscillations de $a$ sur l'ensemble des $q$ segments.

Entrée

La première ligne contient deux entiers $n$ et $q$ ($1 \le n, q \le 2 \cdot 10^5$).

La deuxième ligne contient $n$ entiers $a_1, \dots, a_n$ ($0 \le a_i \le 10^9$) : les éléments du tableau. Ici, $a_i = 0$ signifie que le $i$-ième élément est manquant.

Les $q$ lignes suivantes décrivent les segments. Chacune d'elles contient deux entiers $\ell_i$ et $r_i$ ($1 \le \ell_i \le r_i \le n$).

Sortie

Affichez un seul entier : la somme minimale des oscillations de $a$ sur tous les segments donnés.

Exemples

Entrée 1

5 2
2 1 0 3 2
1 3
3 5

Sortie 1

2

Entrée 2

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

Sortie 2

2

Entrée 3

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

Sortie 3

6

Remarque

Dans le premier exemple, le seul tableau optimal est $a = [2, 1, 2, 3, 2]$.

Dans le deuxième exemple, il existe plusieurs tableaux optimaux. Par exemple, $a = [1, 2, 3, 2, 1]$ est optimal.

Dans le troisième exemple, il existe plusieurs tableaux optimaux. Par exemple, $a = [4, 4, 4, 1, 2, 3, 4]$ est 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.