Universal Cup Judging System

Universal Cup

Limite de temps : 5.0 s Limite de mémoire : 1024 MB Points totaux : 100 Difficulté: [afficher] Hackable ✓
Statistiques

Gefið er fylki $a$ sem samanstendur af $n$ jákvæðum heiltölum. Hins vegar vantar nokkur stök í $a$, og þau hafa verið sett sem núll.

Skilgreinum sveiflu (oscillation) fylkisins $a$ á bili $[\ell, r]$ sem $\max(a_\ell, \dots, a_r) - \min(a_\ell, \dots, a_r)$.

Gefin eru $q$ bil á forminu $[\ell_i, r_i]$. Skiptu hverju núlli í $a$ út fyrir jákvæða heiltölu til að lágmarka summu sveiflna $a$ á öllum $q$ bilunum.

Inntak

Fyrsta línan inniheldur tvær heiltölur $n$ og $q$ ($1 \le n, q \le 2 \cdot 10^5$).

Önnur línan inniheldur $n$ heiltölur $a_1, \dots, a_n$ ($0 \le a_i \le 10^9$): stök fylkisins. Hér þýðir $a_i = 0$ að $i$-ta stakið vanti.

Næstu $q$ línur lýsa bilunum. Hver þeirra inniheldur tvær heiltölur $\ell_i$ og $r_i$ ($1 \le \ell_i \le r_i \le n$).

Úttak

Prentaðu eina heiltölu: lágmarkssummu sveiflna $a$ á öllum gefnu bilunum.

Dæmi

Inntak 1

5 2
2 1 0 3 2
1 3
3 5

Úttak 1

2

Inntak 2

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

Úttak 2

2

Inntak 3

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

Úttak 3

6

Athugasemd

Í fyrsta dæminu er eina besta fylkið $a = [2, 1, 2, 3, 2]$.

Í öðru dæminu eru nokkur bestu fylki. Til dæmis er $a = [1, 2, 3, 2, 1]$ best.

Í þriðja dæminu eru nokkur bestu fylki. Til dæmis er $a = [4, 4, 4, 1, 2, 3, 4]$ best.

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.