Universal Cup Judging System

Universal Cup

حد الوقت: 5.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 الصعوبة: [عرض] قابلة للهجوم ✓
الإحصائيات

Anda diberikan sebuah larik $a$ yang terdiri atas $n$ bilangan bulat positif. Namun, beberapa elemen dari $a$ hilang, dan elemen-elemen tersebut digantikan oleh angka nol.

Definisikan osilasi dari $a$ pada suatu segmen $[\ell, r]$ sebagai $\max(a_\ell, \dots, a_r) - \min(a_\ell, \dots, a_r)$.

Anda diberikan $q$ segmen berbentuk $[\ell_i, r_i]$. Gantilah setiap angka nol di $a$ dengan suatu bilangan bulat positif untuk meminimalkan jumlah osilasi dari $a$ pada semua $q$ segmen tersebut.

Masukan

Baris pertama berisi dua bilangan bulat $n$ dan $q$ ($1 \le n, q \le 2 \cdot 10^5$).

Baris kedua berisi $n$ bilangan bulat $a_1, \dots, a_n$ ($0 \le a_i \le 10^9$): elemen-elemen dari larik. Di sini, $a_i = 0$ berarti bahwa elemen ke-$i$ hilang.

$q$ baris berikutnya mendeskripsikan segmen-segmen tersebut. Masing-masing baris berisi dua bilangan bulat $\ell_i$ dan $r_i$ ($1 \le \ell_i \le r_i \le n$).

Keluaran

Cetaklah satu bilangan bulat: jumlah osilasi minimum dari $a$ pada semua segmen yang diberikan.

Contoh

Masukan 1

5 2
2 1 0 3 2
1 3
3 5

Keluaran 1

2

Masukan 2

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

Keluaran 2

2

Masukan 3

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

Keluaran 3

6

Catatan

Pada contoh pertama, satu-satunya larik yang optimal adalah $a = [2, 1, 2, 3, 2]$.

Pada contoh kedua, terdapat beberapa larik yang optimal. Sebagai contoh, $a = [1, 2, 3, 2, 1]$ adalah optimal.

Pada contoh ketiga, terdapat beberapa larik yang optimal. Sebagai contoh, $a = [4, 4, 4, 1, 2, 3, 4]$ adalah 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.