#1187908 (C++17) No.3665 Two Important Tasks

• 問題: No.3665 Two Important Tasks
• ユーザー: GOTKAKO
• 提出日時: 2026-09-19 06:47:02
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 3,279 bytes
• コンパイル時間: 1,553 ms
• コンパイル使用メモリ: 230,924 KB
• 実行使用メモリ: 56,756 KB
• 最終ジャッジ日時: 2026-09-19 06:47:31
• 合計ジャッジ時間: 8,472 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
sample	AC * 2
other	AC * 12 WA * 11

ソースコード

#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,long long>> LRC(N); 
    vector<vector<int>> Ls(N+1),Rs(N+1);
    for(int i=0; i<N; i++){
        auto &[l,r,c] = LRC.at(i);
        cin >> l >> r >> c,l--;
        for(int d=l; d<r; d++) P.at(d).push_back(i);
        Ls.at(l).push_back(i);
        Rs.at(r).push_back(i);
    }

    auto DP = [&](int l,int r,bool rev) -> vector<long long> {
        int n = r-l;
        vector<long long> dp(n+1);
        if(rev == false){
            for(int i=0; i<n; i++){
                dp.at(i+1) = max(dp.at(i+1),dp.at(i));
                for(auto pos : Ls.at(i+l)){
                    auto &[a,b,c] = LRC.at(pos);
                    if(b <= r) dp.at(b-l) = max(dp.at(b-l),dp.at(i)+c);
                }
            }
        }
        else{
            for(int i=n; i>0; i--){
                dp.at(i-1) = max(dp.at(i-1),dp.at(i));
                for(auto pos : Rs.at(i+l)){
                    auto &[a,b,c] = LRC.at(pos);
                    if(a >= l) dp.at(a-l) = max(dp.at(a-l),dp.at(i)+c);
                }
            }
        }
        return dp;
    };

    vector<long long> answer(Q);
    auto f = [&](auto f,int l,int r,vector<tuple<int,int,int>> Qs) -> void {
        if(Qs.size() == 0) return;
        if(l+1 == r){
            long long big = 0;
            for(auto pos : Ls.at(l)){
                auto [a,b,c] = LRC.at(pos);
                if(b == r) big = max(big,c);
            }
            for(auto [a,b,qpos] : Qs){
                assert(a == l && b == r);
                answer.at(qpos) += big;
                
            }
            return;
        }
        int m = (l+r)/2;
        vector<tuple<int,int,int>> Lq,Rq,Mq;
        for(auto [a,b,qpos] : Qs){
            if(b <= m) Lq.push_back({a,b,qpos});
            else if(a >= m) Rq.push_back({a,b,qpos});
            else Mq.push_back({a,b,qpos});
        }
        f(f,l,m,Lq),f(f,m,r,Rq);
        int n = Mq.size();
        if(n == 0) return;
        vector<long long> best(n);
        for(auto pos : P.at(m)){
            auto [a1,b1,c] = LRC.at(pos);
            if(!(l <= a1 && b1 <= r)) continue;
            auto dpl = DP(l,a1,true),dpr = DP(b1,r,false);
            for(int i=0; i<n; i++){
                auto [a,b,qpos] = Mq.at(i);
                if(a <= a1 && b1 <= b) best.at(i) = max(best.at(i),dpl.at(a-l)+dpr.at(b-b1)+c);
            } 
        }
        for(int i=0; i<n; i++){
            auto [a,b,qpos] = Mq.at(i);
            answer.at(qpos) += best.at(i);
        }
    };

    vector<tuple<int,int,int>> Query;
    auto DPL = DP(0,N,false),DPR = DP(0,N,true);
    for(int i=0; i<Q; i++){
        int a,b; cin >> a >> b,a--,b--;
        auto [l1,r1,c1] = LRC.at(a); 
        auto [l2,r2,c2] = LRC.at(b);
        if(max(l1,l2) < min(r1,r2)) answer.at(i) = -1;
        else{
            answer.at(i) = c1+c2;
            answer.at(i) += DPL.at(min(l1,l2));
            answer.at(i) += DPR.at(max(r1,r2));
            if(max(l1,l2) != min(r1,r2)) Query.push_back({min(r1,r2),max(l1,l2),i});
        }
    }
    f(f,0,N,Query);
    for(auto a : answer) cout << a << "\n";
}