#1181510 (C++23) No.3665 Two Important Tasks

• 問題: No.3665 Two Important Tasks
• ユーザー: lif4635
• 提出日時: 2026-08-30 16:15:24
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0)
• 結果: AC
• 実行時間: 2,298 ms / 4,000 ms
• コード長: 3,376 bytes
• コンパイル時間: 4,301 ms
• コンパイル使用メモリ: 385,756 KB
• 実行使用メモリ: 212,736 KB
• 最終ジャッジ日時: 2026-08-30 16:15:49
• 合計ジャッジ時間: 21,883 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_1

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

ソースコード

// # pragma GCC target("avx2")
// # pragma GCC optimize("O3")
// # pragma GCC optimize("unroll-loops")
#ifdef harurun
#define debug(x) cerr<<#x<<": "<<x<<endl
#else
#define debug(x)
#endif
#include <bits/stdc++.h>
using namespace std;
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
// using mint = modint1000000007;
// using mint = double;
#endif

//define
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<long long , long long>;
using vi = vector<int>;
using vll = vector<long long>;

#define rep(i,l,r) for (int i = (int)(l); i < (int)(r); i++)
#define rrep(i,l,r) for (int i = (int)(r-1); i >= (int)(l); i--)
#define len(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define elif else if
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
const int inf = 1e9;
const long long infl = 1LL<<60;
const int mod = 998244353;
ll pow(ll a, ll b, ll p){ ll ans = 1; while(b){ if(b & 1) (ans *= a) %= p; (a *= a) %= p; b /= 2; } return ans; }
template<class T, class U> bool chmin(T& a, const U& b){ if(a > T(b)){ a = b; return 1; } return 0; }
template<class T, class U> bool chmax(T& a, const U& b){ if(a < T(b)){ a = b; return 1; } return 0; }
template <class T>
using spq = priority_queue<T, vector<T>, greater<T>>;

template<class T>istream& operator>>(istream& i, vector<T>& v) {for(int j = 0; j < (int)(v).size(); j++) i >> v[j]; return i;}
struct IoSetup {
    IoSetup() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(15);
        cerr << fixed << setprecision(15);
    }
} iosetup;


using S = array<array<ll, 6>, 6>;

S e(){
    S a;
    rep(i, 0, 6){
        rep(j, 0, 6){
            a[i][j] = (i == j ? 0 : -infl);
        }
    }
    return a;
}

S op(S x, S y){
    S r;
    rep(i, 0, 6){
        rep(j, 0, 6){
            r[i][j] = -infl;
            rep(k, 0, 6){
                chmax(r[i][j], x[i][k] + y[k][j]);
            }
        }
    }
    return r;
}


void solve(){
    int n, q; cin >> n >> q;
    vi l(n), r(n), col(n); vll c(n);
    vector<pair<int, int>> p(n);
    rep(i, 0, n){
        cin >> l[i] >> r[i] >> c[i]; l[i]--;
        p[i] = {l[i], i};
    }

    sort(all(p));
    vi last(5);
    for (auto [x, i] : p) {
        rep(c, 0, 5){
            if (last[c] <= x) {
                col[i] = c + 1;
                last[c] = r[i];
                break;
            }
        }
    }

    vector<S> a(n);
    for(auto &ai : a){
        rep(i, 0, 6) rep(j, 0, 6) ai[i][j] = -infl;
        ai[0][0] = 0;
    }

    rep(i, 0, n){
        int x = col[i];
        if(l[i] + 1 == r[i]){
            chmax(a[l[i]][0][0], c[i]);
        }else{
            a[l[i]][0][x] = c[i];
            rep(t, l[i] + 1, r[i] - 1) a[t][x][x] = 0;
            a[r[i] - 1][x][0] = 0;
        }
    }

    segtree<S, op, e> seg(a);
    rep(i, 0, q){
        int x, y; cin >> x >> y; x--, y--;

        if(l[x] > l[y]) swap(x, y);
        if(r[x] > l[y]){
            cout << -1 << endl;
            continue;
        }

        ll ans = seg.prod(0, l[x])[0][0] + c[x] + seg.prod(r[x], l[y])[0][0] + c[y] + seg.prod(r[y], n)[0][0];
        cout << ans << endl;
    }
}


int main(){
    int t;
    // cin >> t;
    t = 1;
    while(t--) solve();
    return 0;
}