Overview

When Takahashi descends a mountain, he visits rest spots in strictly decreasing order of elevation, and the goal is to maximize the total scenic score obtained.

Analysis

This problem has the following two constraints:

1. The elevation of every rest spot visited must be strictly lower than the current position \(X\).
2. The order of visits must be in strictly decreasing order of elevation.

First, we can ignore spots that do not satisfy condition 1 (i.e., \(A_i \geq X\)).

Next, we sort the remaining spots in ascending order of elevation. By doing this, the spots are arranged so that elevation increases from left to right, and the problem reduces to “finding a subsequence selected from left to right that maximizes the total score” — essentially finding an increasing subsequence with maximum score sum.

This is a variant of the classic Longest Increasing Subsequence (LIS) problem, where instead of maximizing length, we seek the increasing subsequence with the maximum sum of scores.

A naive DP (dynamic programming) approach would examine all preceding elements for each element to perform updates, resulting in \(O(N^2)\) time complexity. Since \(N\) can be up to \(2 \times 10^5\), this would result in TLE.

Therefore, we speed this up using a BIT (Binary Indexed Tree) or segment tree. This allows us to efficiently retrieve and update the maximum score among positions before a given point, achieving an overall complexity of \(O(N \log N)\).

Algorithm

1. Extract only the rest spots satisfying \(A_i < X\), and sort them in ascending order of elevation.
2. Coordinate compress the elevations of each rest spot so they can be managed on a BIT.
3. Prepare a BIT and for each spot, perform the following:
   • Retrieve the maximum score among spots with lower elevation from the BIT.
   • Compare the value obtained by adding the current spot’s score to that maximum with the current spot’s score alone, and adopt the better one.
   • Update the BIT.
4. Track the overall maximum score while computing the answer.

This algorithm maximizes the total score while respecting the constraint of visiting spots in strictly decreasing order of elevation.

Complexity

• Time complexity: \(O(N \log N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Perform coordinate compression while preserving the relative order of elevations, keeping the BIT size small.

• Note that BIT update and query operations must be performed using 1-indexed values.

• Since spot scores can be negative, handle them appropriately by initializing with \(-\infty\).

• When updating, compare both cases: “selecting only the current spot” and “extending from a previous subsequence.”

  Source Code

import sys
from bisect import bisect_left, bisect_right
import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    X = int(data[1])
    
    spots = []
    for i in range(N):
        a = int(data[2 + 2*i])
        b = int(data[2 + 2*i + 1])
        if a < X:
            spots.append((a, b))
    
    # 標高でソート
    spots.sort()
    
    # dp[i] := 標高が低い方からi番目までのスポットを使ってできる最大スコア
    # 実際に使うのは座標圧縮されたインデックスに対してのDP
    # しかし、この問題では、連続した部分列の中で降順になっているものを選ぶ必要がある
    # つまり、標高順にソートした後、部分列でスコアの和を最大化するような増加部分列（ただしスコアの和を最大化）
    # => 最長増加部分列(LIS)の変形：最大和LIS
    
    n = len(spots)
    if n == 0:
        print(0)
        return

    # 座標圧縮の準備（標高について）
    heights = [spot[0] for spot in spots]
    unique_heights = sorted(set(heights))
    k = len(unique_heights)
    
    # BIT or Segment Tree を使って効率的に処理する
    # dp[h] := 標高 h で終わる経路の最大スコア
    # ただし、h の範囲が大きいので、座標圧縮 + BIT で管理する
    
    class BITMax:
        def __init__(self, size):
            self.size = size
            self.tree = [-float('inf')] * (size + 1)
        
        def update(self, i, x):
            while i <= self.size:
                self.tree[i] = max(self.tree[i], x)
                i += i & -i
        
        def query(self, i):
            res = -float('inf')
            while i > 0:
                res = max(res, self.tree[i])
                i -= i & -i
            return res
    
    bit = BITMax(k)
    max_score = 0
    
    # スポットを標高順に処理（すでにソート済み）
    for a, b in spots:
        idx = bisect_left(unique_heights, a) + 1  # 1-indexed
        # idx よりも標高が低い中での最大値を取得
        prev_max = bit.query(idx - 1)
        current = max(b, prev_max + b)
        bit.update(idx, current)
        max_score = max(max_score, current)
    
    print(max_score)

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.