#1180380 (PyPy3) No.3665 Two Important Tasks

• 問題: No.3665 Two Important Tasks
• ユーザー: tyawanmusi
• 提出日時: 2026-08-30 04:03:55
• 言語: PyPy3 (7.3.23)
• 結果: AC
• 実行時間: 3,479 ms / 4,000 ms
• コード長: 4,500 bytes
• コンパイル時間: 245 ms
• コンパイル使用メモリ: 96,008 KB
• 実行使用メモリ: 446,592 KB
• 最終ジャッジ日時: 2026-08-30 13:07:09
• 合計ジャッジ時間: 21,902 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
sample	AC * 2
other	AC * 23

ソースコード

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def main():
    n, q = map(int, input().split())
    lrc = [list(map(int, input().split())) for _ in range(n)]
    query = [list(map(int, input().split())) for _ in range(q)]

    lrc_left = [[] for _ in range(n + 2)]
    lrc_right = [[] for _ in range(n + 2)]
    cover = [[] for _ in range(n + 2)]
    for i in range(n):
        l, r, c = lrc[i]
        lrc_left[l].append(i)
        lrc_right[r].append(i)
        for j in range(l, r + 1):
            cover[j].append(i)

    # [1,i]
    dp_leftend = [0] * (n + 2)
    for i in range(1, n + 1):
        dp_leftend[i] = dp_leftend[i - 1]
        for j in lrc_right[i]:
            job_l, job_c = lrc[j][0], lrc[j][2]
            dp_leftend[i] = max(dp_leftend[i], job_c + dp_leftend[job_l - 1])

    # [i,N]
    dp_rightend = [0] * (n + 2)
    for i in range(n, 0, -1):
        dp_rightend[i] = dp_rightend[i + 1]
        for j in lrc_left[i]:
            job_r, job_c = lrc[j][1], lrc[j][2]
            dp_rightend[i] = max(dp_rightend[i], job_c + dp_rightend[job_r + 1])

    dp_l = [[] for _ in range(n + 1)]
    dp_r = [[] for _ in range(n + 1)]

    def f(l, r):
        if l > r:
            return
        m = (l + r) >> 1
        left_start = {m}
        right_start = {m + 1}
        for i in cover[m]:
            job_l, job_r = lrc[i][0], lrc[i][1]
            if l <= job_l and job_r <= r:
                if l <= lrc[i][0] - 1:
                    left_start.add(lrc[i][0] - 1)
                if lrc[i][1] + 1 <= r:
                    right_start.add(lrc[i][1] + 1)
        left_start = list(left_start)
        right_start = list(right_start)
        
        for s in left_start:
            dp = [0] * (s - l + 2)
            for i in range(s, l - 1, -1):
                res = dp[i + 1 - l]
                for j in lrc_left[i]:
                    job_r, job_c = lrc[j][1], lrc[j][2]
                    if job_r <= s:
                        res = max(res, job_c + dp[job_r + 1 - l])
                dp[i - l] = res
            dp_l[m].append((s, dp))
            
        for s in right_start:
            dp = [0] * (r - s + 2)
            for i in range(s, r + 1):
                res = dp[i - 1 - s] if i > s else 0
                for j in lrc_right[i]:
                    job_l, job_c = lrc[j][0], lrc[j][2]
                    if job_l >= s:
                        prev = dp[job_l - 1 - s] if job_l > s else 0
                        res = max(res, job_c + prev)
                dp[i - s] = res
            dp_r[m].append((s, dp))

        f(l, m - 1)
        f(m + 1, r)
    f(1, n)

    def solve(L, R):
        if L > R:
            return 0
        m = (L + R) >> 1
        l, r = 1, n
        while l <= r:
            m = (l + r) >> 1
            if R < m:
                r = m - 1
            elif L > m:
                l = m + 1
            else:
                ans = 0
                for s, dp in dp_l[m]:
                    if s == m:
                        ans += dp[L - l]
                        break
                for s, dp in dp_r[m]:
                    if s == m + 1:
                        ans += dp[R - s]
                        break
                
                for i in cover[m]:
                    job_l, job_r, job_c = lrc[i]
                    if l <= job_l and job_r <= r:
                        if L <= job_l and job_r <= R:
                            tmp_l = 0
                            for s, dp in dp_l[m]:
                                if s == job_l - 1 and L <= job_l - 1:
                                    tmp_l = dp[L - l]
                                    break
                            tmp_r = 0
                            for s, dp in dp_r[m]:
                                if s == job_r + 1 and R >= job_r + 1:
                                    tmp_r = dp[R - s]
                                    break
                                    
                            ans = max(ans, tmp_l + job_c + tmp_r)
                return ans
        return 0

    for a, b in query:
        la, ra, ca = lrc[a - 1]
        lb, rb, cb = lrc[b - 1]
        
        if max(la, lb) <= min(ra, rb):
            print(-1)
            continue

        if la > lb:
            la, ra, ca, lb, rb, cb = lb, rb, cb, la, ra, ca
    
        ans = ca + cb + dp_leftend[la - 1] + dp_rightend[rb + 1]
        ans += solve(ra + 1, lb - 1)
        print(ans)

if __name__ == "__main__":
    main()