#1180379 (PyPy3) No.3665 Two Important Tasks

• 問題: No.3665 Two Important Tasks
• ユーザー: tyawanmusi
• 提出日時: 2026-08-30 03:58:40
• 言語: PyPy3 (7.3.23)
• 結果: AC
• 実行時間: 3,505 ms / 4,000 ms
• コード長: 4,460 bytes
• コンパイル時間: 238 ms
• コンパイル使用メモリ: 95,980 KB
• 実行使用メモリ: 465,540 KB
• 最終ジャッジ日時: 2026-08-30 13:06:50
• 合計ジャッジ時間: 21,544 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

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

ソースコード

import sys
input = sys.stdin.readline

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_l_id = [[] for _ in range(n + 1)]
dp_r = [[] for _ in range(n + 1)]
dp_r_id = [[] for _ in range(n + 1)]

def f(l, r):
    if l > r:
        return
    m = (l + r) // 2
    jobs = []
    for i in cover[m]:
        job_l, job_r = lrc[i][0], lrc[i][1]
        if l <= job_l and job_r <= r:
            jobs.append(i)

    left_start = {m}
    right_start = {m + 1}
    for i in jobs:
        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 = sorted(list(left_start))
    right_start = sorted(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(dp)
        dp_l_id[m].append(s)
        
    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(dp)
        dp_r_id[m].append(s)

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

def solve(L, R):
    if L > R:
        return 0
    m = (L + R) // 2
    l, r = 1, n
    while l <= r:
        m = (l + r) // 2
        if R < m:
            r = m - 1
        elif L > m:
            l = m + 1
        else:
            ans = 0
            for i in range(len(dp_l[m])):
                s = dp_l_id[m][i]
                dp = dp_l[m][i]
                if s == m:
                    ans += dp[L - l]
                    break
            for i in range(len(dp_r[m])):
                s = dp_r_id[m][i]
                dp = dp_r[m][i]
                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 i in range(len(dp_l[m])):
                            s = dp_l_id[m][i]
                            dp = dp_l[m][i]
                            if s == job_l - 1 and L <= job_l - 1:
                                tmp_l = dp[L - l]
                                break
                        tmp_r = 0
                        for i in range(len(dp_r[m])):
                            s = dp_r_id[m][i]
                            dp = dp_r[m][i]
                            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)