結果

問題 No.3665 Two Important Tasks
コンテスト
ユーザー GOTKAKO
提出日時 2026-08-30 18:10:16
言語 C++17
(gcc 15.3.0 + boost 1.92.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 1,508 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,333 ms
コンパイル使用メモリ 226,700 KB
実行使用メモリ 383,464 KB
最終ジャッジ日時 2026-08-30 18:10:41
合計ジャッジ時間 8,034 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 12 TLE * 1 -- * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N,Q; cin >> N >> Q;
    vector<vector<int>> P(N);
    vector<tuple<int,int,int>> LRC(N);
    for(int i=0; i<N; i++){
        int l,r,c; cin >> l >> r >> c,l--;
        for(int p=l; p<r; p++) P.at(p).push_back(i);
        LRC.at(i) = {l,r,c};
    }

    vector<long long> one(N,-1);
    unordered_map<long long,long long> memo;
    auto f = [&](auto f,int l,int r) -> long long {
        if(l >= r) return 0;
        if(l+1 == r){
            if(one.at(l) != -1) return one.at(l);
            int now = 0;
            for(auto pos : P.at(l)){
                auto [L,R,c] = LRC.at(pos);
                if(l == L && r == R) now = max(now,c);
            }
            return one.at(l) = now;
        }
        if(memo.count({l*1001001LL+r})) return memo[{l*1001001LL+r}];

        int m = (l+r)/2;

        long long ret = f(f,l,m)+f(f,m,r);
        for(auto pos : P.at(m)){
            auto [L,R,c] = LRC.at(pos);
            if(l <= L && L < m && m < R && R <= r) ret = max(ret,c+f(f,l,L)+f(f,R,r)); 
        }
        memo[l*1001001LL+r] = ret;
        return ret;
    };

    while(Q--){
        int a,b; cin >> a >> b,a--,b--;
        auto [l1,r1,c1] = LRC.at(a);
        auto [l2,r2,c2] = LRC.at(b);
        if(l1 > l2) swap(l1,l2),swap(r1,r2),swap(c1,c2);
        if(l2 < r1){cout << "-1\n"; continue;}


        cout << f(f,0,l1)+f(f,r1,l2)+f(f,r2,N)+c1+c2 << "\n";
    }
}
0