시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4.5 초 512 MB 3 2 2 100.000%

문제

There are N mountains lying in a horizontal row, numbered from 0 through N - 1from left to right. The height of the mountain i is Hi (0 ≤ iN - 1). Exactly one person lives on the top of each mountain.

You are going to hold Q meetings, numbered from 0 through Q - 1. The meeting j (0 ≤ jQ - 1) will be attended by all the people living on the mountains from Lj to Rj, inclusive (0 ≤ LjRjN - 1). For this meeting, you must select a mountain x as the meeting place (LjxRj). The cost of this meeting, based on your selection, is then calculated as follows:

  • The cost of the participant from each mountain y (LjyRj) is the maximum height of the mountains between the mountains x and y, inclusive. In particular, the cost of the participant from the mountain x is Hx, the height of the mountain x.
  • The cost of the meeting is the sum of the costs of all participants.

For each meeting, you want to find the minimum possible cost of holding it.

Note that all participants go back to their own mountains after each meeting; so the cost of a meeting is not influenced by the previous meetings.

구현

You should implement the following function:

int64[] minimum_costs(int[] H, int[] L, int[] R)
  • H: an array of length N, representing the heights of the mountains.
  • L and R: arrays of length Q, representing the range of the participants in the meetings.
  • This function should return an array C of length Q. The value of Cj (0 ≤ jQ - 1) must be the minimum possible cost of holding the meeting j.
  • Note that the values of N and Q are the lengths of the arrays, and can be obtained as indicated in the implementation notice.

예제

Let N = 4, H = [2, 4, 3, 5], Q = 2, L = [0, 1], and R = [2, 3].

The grader calls minimum_costs([2, 4, 3, 5], [0, 1], [2, 3]).

The meeting j = 0 has Lj = 0 and Rj = 2, so will be attended by the people living on the mountains 0, 1, and 2. If the mountain 0 is chosen as the meeting place, the cost of the meeting 0 is calculated as follows:

  • The cost of the participant from the mountain 0 is max{H0} = 2.
  • The cost of the participant from the mountain 1 is max{H0, H1} = 4.
  • The cost of the participant from the mountain 2 is max{H0, H1, H2} = 4.
  • Therefore, the cost of the meeting 0 is 2 + 4 + 4 = 10.

It is impossible to hold the meeting 0 at a lower cost, so the minimum cost of the meeting 0 is 10.

The meeting j = 1 has Lj = 1 and Rj = 3, so will be attended by the people living on the mountains 1, 2, and 3. If the mountain 2 is chosen as the meeting place, the cost of the meeting 1 is calculated as follows:

  • The cost of the participant from the mountain 1 is max{H1, H2} = 4.
  • The cost of the participant from the mountain 2 is max{H2} = 3.
  • The cost of the participant from the mountain 3 is max{H2, H3} = 5.
  • Therefore, the cost of the meeting 1 is 4 + 3 + 5 = 12.

It is impossible to hold the meeting 1 at a lower cost, so the minimum cost of the meeting 1 is 12.

제한

  • 1 ≤ N ≤ 750,000
  • 1 ≤ Q ≤ 750,000
  • 1 ≤ Hi ≤ 1,000,000,000 (0 ≤ iN - 1)
  • 0 ≤ LjRjN - 1 (0 ≤ jQ - 1)
  • (Lj, Rj) ≠ (Lk, Rk) (0 ≤ j < kQ - 1)

서브태스크

번호 배점 조건
1 4

N ≤ 3,000, Q ≤ 10

2 15

N ≤ 5,000, Q ≤ 5,000

3 17

N ≤ 100,000, Q ≤ 100,000, Hi ≤ 2 (0 ≤ iN - 1)

4 24

N ≤ 100,000, Q ≤ 100,000, Hi ≤ 20 (0 ≤ iN - 1)

5 40

No additional constraints

샘플 그레이더

The sample grader reads the input in the following format:

  • line 1: N Q
  • line 2: H0 H1 ... HN-1
  • line 3 + j (0 ≤ jQ - 1): Lj Rj

The sample grader prints the return value of minimum_costs in the following format:

  • line 1 + j (0 ≤ jQ - 1): Cj

제출할 수 있는 언어

C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)

채점 및 기타 정보

  • 예제는 채점하지 않는다.