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

$n$ 個の正整数からなる配列 $a$ が与えられます。ただし、$a$ の一部の要素は欠損しており、代わりに $0$ に置き換えられています。

区間 $[\ell, r]$ における $a$ の振幅(oscillation)を $\max(a_\ell, \dots, a_r) - \min(a_\ell, \dots, a_r)$ と定義します。

$[\ell_i, r_i]$ の形をした $q$ 個の区間が与えられます。すべての $q$ 個の区間における $a$ の振幅の総和が最小になるように、$a$ に含まれる各 $0$ をそれぞれある正整数に置き換えてください。

入力

1 行目には 2 つの整数 $n$ と $q$($1 \le n, q \le 2 \cdot 10^5$)が与えられます。

2 行目には配列の要素を表す $n$ 個の整数 $a_1, \dots, a_n$($0 \le a_i \le 10^9$)が与えられます。ここで、$a_i = 0$ は $i$ 番目の要素が欠損していることを意味します。

続く $q$ 行には区間が記述されています。各行には 2 つの整数 $\ell_i$ と $r_i$($1 \le \ell_i \le r_i \le n$)が与えられます。

出力

与えられたすべての区間における $a$ の振幅の総和の最小値を表す 1 つの整数を出力してください。

入出力例

入力 1

5 2
2 1 0 3 2
1 3
3 5

出力 1

2

入力 2

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

出力 2

2

入力 3

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

出力 3

6

注記

1 番目の例では、唯一の最適な配列は $a = [2, 1, 2, 3, 2]$ です。

2 番目の例では、最適な配列が複数存在します。例えば、$a = [1, 2, 3, 2, 1]$ は最適です。

3 番目の例では、最適な配列が複数存在します。例えば、$a = [4, 4, 4, 1, 2, 3, 4]$ は最適です。

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.