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

• 問題: No.3665 Two Important Tasks
• ユーザー: Nzt3
• 提出日時: 2026-09-08 00:43:24
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 4,914 bytes
• コンパイル時間: 2,952 ms
• コンパイル使用メモリ: 359,348 KB
• 実行使用メモリ: 108,252 KB
• 最終ジャッジ日時: 2026-09-08 00:44:06
• 合計ジャッジ時間: 24,029 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

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

ソースコード

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

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
#define rep3(i, a, b, c) for (ll i = (a); i < (b); i += (c))
#define rep2(i, a, b) rep3(i, a, b, 1)
#define rep1(i, n) rep2(i, 0, n)
#define rep0(n) rep1(aaaaa, n)
#define ov4(a, b, c, d, name, ...) name
#define rep(...) ov4(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define per(i, a, b) for (ll i = (a) - 1; i >= (b); i--)
#define fore(e, v) for (auto &&e : v)
#define all(a) begin(a), end(a)
#define sz(a) (ssize(a))
#define lb(v, x) (lower_bound(all(v), x) - begin(v))
#define eb emplace_back

template <typename T, typename S> bool chmin(T &a, const S &b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T, typename S> bool chmax(T &a, const S &b) {
  return a < b ? a = b, 1 : 0;
}
const int INF = 1e9 + 100;
const ll INFL = 3e18 + 100;
#define i128 __int128_t
struct _ {
  _() { cin.tie(0)->sync_with_stdio(0), cout.tie(0); }
} __;

using al3 = array<ll, 3>;
vector<al3> tasks;

struct lrval {
  int left, right;
  bool solo;
  ll val;
};
struct S {
  int l, r;
  vector<lrval> v;
};

S seg_e() { return S{-1, -1, {lrval{-1, -1, 0, 0}}}; }

S seg_op(const S a, const S b) {
  if (a.l == -1)
    return b;
  if (b.l == -1)
    return a;
  S ret{a.l, b.r, {}};
  vector<lrval> d;
  for (auto i : a.v) {
    for (auto j : b.v) {
      if (i.right == j.left) {
        if (i.right == -1) {
          d.push_back(lrval{i.left, j.right, 0, i.val + j.val});
        } else {
          if (i.solo) {
            if (j.solo) {
              if (a.l <= tasks[i.right][0] && tasks[i.right][1] <= b.r) {
                d.push_back(
                    lrval{-1, -1, 0, i.val + j.val + tasks[i.right][2]});
              } else {
                d.push_back(lrval{i.left, j.right, 1, i.val + j.val});
              }
            } else {
              if (a.l <= tasks[i.right][0] && tasks[i.right][1] <= b.r) {
                d.push_back(
                    lrval{-1, j.right, 0, i.val + j.val + tasks[i.right][2]});
              } else {
                d.push_back(lrval{i.left, j.right, 0, i.val + j.val});
              }
            }
          } else {
            if (j.solo) {
              if (a.l <= tasks[i.right][0] && tasks[i.right][1] <= b.r) {
                d.push_back(
                    lrval{i.left, -1, 0, i.val + j.val + tasks[i.right][2]});
              } else {
                d.push_back(lrval{i.left, j.right, 0, i.val + j.val});
              }
            } else {
              d.push_back(
                  lrval{i.left, j.right, 0, i.val + j.val + tasks[i.right][2]});
            }
          }
        }
      } else {
        if (i.solo) {
          if (j.solo) {
            d.push_back(lrval{-1, -1, false, i.val + j.val});
          } else {
            d.push_back(lrval{-1, j.right, false, i.val + j.val});
          }
        } else {
          if (j.solo) {
            d.push_back(lrval{i.left, -1, false, i.val + j.val});
          } else {
            d.push_back(lrval{i.left, j.right, false, i.val + j.val});
          }
        }
      }
    }
  }
  sort(all(d), [&](const lrval &f, const lrval &g) { return f.val > g.val; });
  set<ll> used;
  fore(i, d) {
    if (!used.contains((i.left) * (1ll << 30) + (i.right))) {
      ret.v.push_back(i);
      used.insert((i.left) * (1ll << 30) + (i.right));
    }
  }
  return ret;
}

int main() {
  int N, Q;
  cin >> N >> Q;
  atcoder::segtree<S, seg_op, seg_e> seg(N);
  tasks.resize(N);
  vector<vi> cover(N);
  rep(i, N) {
    cin >> tasks[i][0] >> tasks[i][1] >> tasks[i][2];
    tasks[i][0]--;
    rep(x, tasks[i][0], tasks[i][1]) { cover[x].push_back(i); }
  }
  rep(i, N) {
    vector<lrval> x;
    ll zs = 0;
    for (auto v : cover[i]) {
      if (tasks[v][0] + 1 == tasks[v][1]) {
        chmax(zs, tasks[v][2]);
      } else {
        x.push_back(lrval{v, v, true, 0});
      }
    }
    x.push_back(lrval{-1, -1, false, zs});
    seg.set(i, S{(int)i, (int)i + 1, x});
  }
  // rep(i, N) {
  //   rep(j, i, N) {
  //     cerr << format("{} {}: \n", i, j);
  //     for (auto i : seg.prod(i, j).v) {
  //       cerr << format("{} {} {}, ", i.left, i.right, i.val);
  //     }
  //     cerr << endl;
  //   }
  // }

  rep(Q) {
    int A, B;
    cin >> A >> B;
    --A, --B;
    if (min(tasks[A][1], tasks[B][1]) > max(tasks[A][0], tasks[B][0])) {
      cout << "-1\n";
      continue;
    }
    if (tasks[A][0] > tasks[B][0])
      swap(A, B);
    ll pre = 0, suf = 0, mid = 0;
    for (auto i : seg.prod(0, tasks[A][0]).v) {
      chmax(pre, i.val);
    }
    for (auto i : seg.prod(tasks[A][1], tasks[B][0]).v) {
      chmax(mid, i.val);
    }
    for (auto i : seg.prod(tasks[B][1], N).v) {
      chmax(suf, i.val);
    }
    cout << pre + mid + suf + tasks[A][2] + tasks[B][2] << '\n';
  }
}