結果

問題 No.3665 Two Important Tasks
コンテスト
ユーザー tyawanmusi
提出日時 2026-08-30 03:52:08
言語 PyPy3
(7.3.23)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 4,503 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 243 ms
コンパイル使用メモリ 96,104 KB
実行使用メモリ 497,668 KB
最終ジャッジ日時 2026-08-30 13:06:20
合計ジャッジ時間 16,227 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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)]

stack = [(1, n)]
for l, r in stack:
    if l > r:
        continue
    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)

    stack.append((l, m - 1))
    stack.append((m + 1, r))

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)
0