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

• 問題: No.3665 Two Important Tasks
• ユーザー: ei1333333
• 提出日時: 2026-08-30 14:16:21
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0)
• 結果: AC
• 実行時間: 1,000 ms / 4,000 ms
• コード長: 9,916 bytes
• コンパイル時間: 5,006 ms
• コンパイル使用メモリ: 398,240 KB
• 実行使用メモリ: 236,160 KB
• 最終ジャッジ日時: 2026-08-30 14:16:43
• 合計ジャッジ時間: 16,034 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

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

ソースコード

#line 1 "template/template.hpp"
#include <bits/stdc++.h>

#if __has_include(<atcoder/all>)
#include <atcoder/all>

#endif

using namespace std;

using int64 = long long;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;

template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
  os << p.first << " " << p.second;
  return os;
}

template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
  is >> p.first >> p.second;
  return is;
}

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  for (size_t i = 0; i < v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& in : v) is >> in;
  return is;
}

template <typename T1, typename T2>
bool chmax(T1& a, T2 b) {
  return a < b && (a = b, true);
}

template <typename T1, typename T2>
bool chmin(T1& a, T2 b) {
  return a > b && (a = b, true);
}

template <typename T = int64>
vector<T> make_v(size_t a) {
  return vector<T>(a);
}

template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
  return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

template <typename T, typename V>
enable_if_t<is_class_v<T> == 0> fill_v(T& t, const V& v) {
  t = v;
}

template <typename T, typename V>
enable_if_t<is_class_v<T> != 0> fill_v(T& t, const V& v) {
  for (auto& e : t) fill_v(e, v);
}

template <typename F>
struct FixPoint : F {
  explicit FixPoint(F&& f) : F(std::forward<F>(f)) {}

  template <typename... Args>
  decltype(auto) operator()(Args&&... args) const {
    return F::operator()(*this, std::forward<Args>(args)...);
  }
};

template <typename F>
decltype(auto) MFP(F&& f) {
  return FixPoint<F>{std::forward<F>(f)};
}

#line 2 "structure/segment-tree/segment-tree.hpp"

#include <cassert>
#include <optional>
#include <vector>

#line 2 "structure/class/monoid.hpp"

template <typename S2, typename Op, typename E>
struct LambdaMonoid {
  using S = S2;
  S op(const S& a, const S& b) const { return _op(a, b); }

  S e() const { return _e(); }

  LambdaMonoid(Op _op, E _e) : _op(_op), _e(_e) {}

 private:
  Op _op;

  E _e;
};

template <typename Op, typename E>
LambdaMonoid(Op _op, E _e) -> LambdaMonoid<decltype(_e()), Op, E>;

/*
struct Monoid {
  using S = ?;
  static constexpr S op(const S& a, const S& b) {}
  static constexpr S e() {}
};
*/
#line 8 "structure/segment-tree/segment-tree.hpp"

template <typename Monoid>
struct SegmentTree {
  using S = typename Monoid::S;

 private:
  int n, sz;

  std::vector<S> seg;

  Monoid m;

 public:
  SegmentTree() = default;

  explicit SegmentTree(Monoid m, int n) : m(m), n(n) {
    sz = 1;
    while (sz < n) sz <<= 1;
    seg.assign(2 * sz, m.e());
  }

  explicit SegmentTree(Monoid m, const std::vector<S>& v)
      : SegmentTree(m, (int)v.size()) {
    build(v);
  }

  void build(const std::vector<S>& v) {
    assert(n == (int)v.size());
    for (int k = 0; k < n; k++) seg[k + sz] = v[k];
    for (int k = sz - 1; k > 0; k--) {
      seg[k] = m.op(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  void set(int k, const S& x) {
    k += sz;
    seg[k] = x;
    while (k >>= 1) {
      seg[k] = m.op(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  S get(int k) const { return seg[k + sz]; }

  S operator[](int k) const { return get(k); }

  void apply(int k, const S& x) {
    k += sz;
    seg[k] = m.op(seg[k], x);
    while (k >>= 1) {
      seg[k] = m.op(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  S prod(int l, int r) const {
    if (l >= r) return m.e();
    S L = m.e(), R = m.e();
    for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
      if (l & 1) L = m.op(L, seg[l++]);
      if (r & 1) R = m.op(seg[--r], R);
    }
    return m.op(L, R);
  }

  S all_prod() const { return seg[1]; }

  template <typename C>
  std::optional<int> find_first(int l, const C& check) const {
    if (l >= n) return std::nullopt;
    l += sz;
    S sum = m.e();
    do {
      while ((l & 1) == 0) l >>= 1;
      if (check(m.op(sum, seg[l]))) {
        while (l < sz) {
          l <<= 1;
          auto nxt = m.op(sum, seg[l]);
          if (not check(nxt)) {
            sum = nxt;
            l++;
          }
        }
        return l + 1 - sz;
      }
      sum = m.op(sum, seg[l++]);
    } while ((l & -l) != l);
    return std::nullopt;
  }

  template <typename C>
  std::optional<int> find_last(int r, const C& check) const {
    if (r <= 0) return std::nullopt;
    r += sz;
    S sum = m.e();
    do {
      r--;
      while (r > 1 and (r & 1)) r >>= 1;
      if (check(m.op(seg[r], sum))) {
        while (r < sz) {
          r = (r << 1) + 1;
          auto nxt = m.op(seg[r], sum);
          if (not check(nxt)) {
            sum = nxt;
            r--;
          }
        }
        return r - sz;
      }
      sum = m.op(seg[r], sum);
    } while ((r & -r) != r);
    return std::nullopt;
  }
};

#line 2 "math/matrix/square-matrix.hpp"

#include <array>
#include <cstddef>
#include <cstdint>
#include <iostream>

/**
 * @brief Square-Matrix(正方行列)
 */
template <class T, std::size_t N>
struct SquareMatrix {
  std::array<std::array<T, N>, N> A;

  SquareMatrix() : A{{}} {}

  SquareMatrix(const std::array<std::array<T, N>, N>& A) : A(A) {}

  std::size_t size() const { return N; }

  inline const std::array<T, N>& operator[](int k) const { return (A.at(k)); }

  inline std::array<T, N>& operator[](int k) { return (A.at(k)); }

  static SquareMatrix add_identity() { return SquareMatrix(); }

  static SquareMatrix mul_identity() {
    SquareMatrix mat;
    for (std::size_t i = 0; i < N; i++) mat[i][i] = 1;
    return mat;
  }

  SquareMatrix& operator+=(const SquareMatrix& B) {
    for (std::size_t i = 0; i < N; i++) {
      for (std::size_t j = 0; j < N; j++) {
        (*this)[i][j] += B[i][j];
      }
    }
    return *this;
  }

  SquareMatrix& operator-=(const SquareMatrix& B) {
    for (std::size_t i = 0; i < N; i++) {
      for (std::size_t j = 0; j < N; j++) {
        (*this)[i][j] -= B[i][j];
      }
    }
    return *this;
  }

  SquareMatrix& operator*=(const SquareMatrix& B) {
    std::array<std::array<T, N>, N> C;
    for (std::size_t i = 0; i < N; i++) {
      for (std::size_t j = 0; j < N; j++) {
        for (std::size_t k = 0; k < N; k++) {
          C[i][j] = (C[i][j] + (*this)[i][k] * B[k][j]);
        }
      }
    }
    A.swap(C);
    return (*this);
  }

  SquareMatrix& operator^=(std::uint64_t k) {
    SquareMatrix B = SquareMatrix::mul_identity();
    while (k > 0) {
      if (k & 1) B *= *this;
      *this *= *this;
      k >>= 1LL;
    }
    A.swap(B.A);
    return *this;
  }

  SquareMatrix operator+(const SquareMatrix& B) const {
    return SquareMatrix(*this) += B;
  }

  SquareMatrix operator-(const SquareMatrix& B) const {
    return SquareMatrix(*this) -= B;
  }

  SquareMatrix operator*(const SquareMatrix& B) const {
    return SquareMatrix(*this) *= B;
  }

  SquareMatrix operator^(std::uint64_t k) const {
    return SquareMatrix(*this) ^= k;
  }

  friend std::ostream& operator<<(std::ostream& os, SquareMatrix& p) {
    for (int i = 0; i < N; i++) {
      os << "[";
      for (int j = 0; j < N; j++) {
        os << p[i][j] << (j + 1 == N ? "]\n" : ",");
      }
    }
    return os;
  }
};


int main() {
  int N, Q;
  cin >> N >> Q;
  vector< int > L(N), R(N), C(N), color(N);
  vector< vector< int > > from(N), to(N + 1);
  for (int i = 0; i < N; i++) {
    cin >> L[i] >> R[i] >> C[i];
    --L[i];
    from[L[i]].emplace_back(i);
    to[R[i]].emplace_back(i);
  }

  vector< int > ord(N);
  iota(ord.begin(), ord.end(), 0);
  ranges::sort(ord, [&](int a, int b) {
    return L[a] < L[b];
  });
  {
    vector buf(5, -1);
    for (auto i : ord) {
      for (int j = 0; j < 5; j++) {
        if (buf[j] <= L[i]) {
          buf[j] = R[i];
          color[i] = j;
          break;
        }
      }
    }
  }
  vector< int64 > pre(N + 1), suf(N + 1);
  for (int i = 1; i <= N; i++) {
    pre[i] = pre[i - 1];
    for (auto& j : to[i]) {
      chmax(pre[i], pre[L[j]] + C[j]);
    }
  }
  for (int i = N - 1; i >= 0; i--) {
    suf[i] = suf[i + 1];
    for (auto& j : from[i]) {
      chmax(suf[i], suf[R[j]] + C[j]);
    }
  }
  using Mat = SquareMatrix< int64, 6 >;
  vector <Mat > init(N);
  Mat e;
  for (int i = 0; i < 6; i++) {
    for (int j = 0; j < 6; j++) {
      e[i][j] = i == j ? 0 : -infll;
    }
  }
  for (int i = 0; i < N; i++) {
    Mat mat;
    for (int j = 0; j < 6; j++) {
      for (int k = 0; k < 6; k++) {
        mat[j][k] = -infll;
      }
    }
    vector< int > ends(5);
    for (auto j : to[i + 1]) {
      ends[color[j]] = 1;
    }
    for (int s = 0; s < 6; s++) {
      int t = s;
      if (s < 5 and ends[s]) t = 5;
      mat[s][t] = 0;
    }
    for (auto j : from[i]) {
      int s = 5;
      int t = color[j];
      if (R[j] == i + 1) t = 5;
      chmax(mat[s][t], C[j]);
    }
    init[i] = mat;
  }
  auto f = [&](const Mat& a, const Mat& b) {
    Mat c = e;
    for (int j = 0; j < 6; j++) {
      for (int k = 0; k < 6; k++) {
        c[j][k] = -infll;
      }
    }
    for (int i = 0; i < 6; i++) {
      for (int j = 0; j < 6; j++) {
        for (int k = 0; k < 6; k++) {
          chmax(c[i][k], a[i][j] + b[j][k]);
        }
      }
    }
    return c;
  };
  auto ep = [&] { return e; };
  auto seg = SegmentTree(LambdaMonoid(f, ep), init);
  while (Q--) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    if (max(L[a], L[b]) < min(R[a], R[b])) {
      cout << -1 << "\n";
      continue;
    }
    if (L[a] > L[b]) {
      swap(a, b);
    }
    cout << pre[L[a]] + C[a] + seg.prod(R[a], L[b])[5][5] + C[b] + suf[R[b]] << "\n";
  }
}