#1187137 (C++23) No.3748 Three Pruning Order

• 問題: No.3748 Three Pruning Order
• ユーザー: ponjuice
• 提出日時: 2026-09-17 04:39:02
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 618 ms / 2,000 ms
• コード長: 6,328 bytes
• コンパイル時間: 3,115 ms
• コンパイル使用メモリ: 355,848 KB
• 実行使用メモリ: 83,324 KB
• 最終ジャッジ日時: 2026-09-25 20:55:51
• 合計ジャッジ時間: 18,814 ms
• ジャッジサーバーID （参考情報）: judge4_1 / judge3_0

ファイルパターン	結果
sample	AC * 1
other	AC * 42

ソースコード

#include<bits/stdc++.h>
using namespace std;
#line 2 "data-structure-2d/dynamic-binary-indexed-tree-2d.hpp"

#line 2 "data-structure/dynamic-binary-indexed-tree.hpp"

#line 2 "data-structure/hash-map-variable-length.hpp"

template <typename Key, typename Val>
struct HashMap {
  using u32 = uint32_t;
  using u64 = uint64_t;

  u32 cap, s;
  vector<Key> keys;
  vector<Val> vals;
  vector<bool> flag;
  u64 r;
  u32 shift;
  Val DefaultValue;

  static u64 rng() {
    u64 m = chrono::duration_cast<chrono::nanoseconds>(
                chrono::high_resolution_clock::now().time_since_epoch())
                .count();
    m ^= m >> 16;
    m ^= m << 32;
    return m;
  }

  void reallocate() {
    cap <<= 1;
    vector<Key> k(cap);
    vector<Val> v(cap);
    vector<bool> f(cap);
    u32 sh = shift - 1;
    for (int i = 0; i < (int)flag.size(); i++) {
      if (flag[i]) {
        u32 hash = (u64(keys[i]) * r) >> sh;
        while (f[hash]) hash = (hash + 1) & (cap - 1);
        k[hash] = keys[i];
        v[hash] = vals[i];
        f[hash] = 1;
      }
    }
    keys.swap(k);
    vals.swap(v);
    flag.swap(f);
    --shift;
  }

  explicit HashMap()
      : cap(8),
        s(0),
        keys(cap),
        vals(cap),
        flag(cap),
        r(rng()),
        shift(64 - __lg(cap)),
        DefaultValue(Val()) {}

  Val& operator[](const Key& i) {
    u32 hash = (u64(i) * r) >> shift;
    while (true) {
      if (!flag[hash]) {
        if (s + s / 4 >= cap) {
          reallocate();
          return (*this)[i];
        }
        keys[hash] = i;
        flag[hash] = 1;
        ++s;
        return vals[hash] = DefaultValue;
      }
      if (keys[hash] == i) return vals[hash];
      hash = (hash + 1) & (cap - 1);
    }
  }

  // exist -> return pointer of Val
  // not exist -> return nullptr
  const Val* find(const Key& i) const {
    u32 hash = (u64(i) * r) >> shift;
    while (true) {
      if (!flag[hash]) return nullptr;
      if (keys[hash] == i) return &(vals[hash]);
      hash = (hash + 1) & (cap - 1);
    }
  }

  // return vector< pair<const Key&, val& > >
  vector<pair<Key, Val>> enumerate() const {
    vector<pair<Key, Val>> ret;
    for (u32 i = 0; i < cap; ++i)
      if (flag[i]) ret.emplace_back(keys[i], vals[i]);
    return ret;
  }

  int size() const { return s; }

  // set default_value
  void set_default(const Val& val) { DefaultValue = val; }
};

/**
 * @brief Hash Map(可変長版)
 * @docs docs/data-structure/hash-map.md
 */
#line 4 "data-structure/dynamic-binary-indexed-tree.hpp"

template <typename S, typename T>
struct DynamicFenwickTree {
  S N;
  HashMap<S, T> data;
  explicit DynamicFenwickTree() = default;
  explicit DynamicFenwickTree(S size) { N = size + 1; }

  void add(S k, T x) {
    for (++k; k < N; k += k & -k) data[k] += x;
  }

  // [0, k)
  T sum(S k) const {
    if (k < 0) return 0;
    T ret = T();
    for (; k > 0; k -= k & -k) {
      const T* p = data.find(k);
      ret += p ? *p : T();
    }
    return ret;
  }

  // [a, b)
  T sum(S a, S b) const { return sum(b) - sum(a); }

  T operator[](S k) const { return sum(k + 1) - sum(k); }

  S lower_bound(T w) {
    if (w <= 0) return 0;
    S x = 0;
    for (S k = 1 << __lg(N); k; k >>= 1) {
      if (x + k <= N - 1 && data[x + k] < w) {
        w -= data[x + k];
        x += k;
      }
    }
    return x;
  }
};

/**
 * @brief 動的Binary Indexed Tree
 * @docs docs/data-structure/dynamic-binary-indexed-tree.md
 */
#line 4 "data-structure-2d/dynamic-binary-indexed-tree-2d.hpp"

template <typename T>
struct DynamicFenwickTree2D {
  using BIT = DynamicFenwickTree<int, T>;
  int N, M;
  vector<BIT*> bit;
  DynamicFenwickTree2D() = default;
  DynamicFenwickTree2D(int n, int m) : N(n + 1), M(m) {
    for (int _ = 0; _ < N; ++_) bit.push_back(new BIT(M));
  }
  
  void add(int i, int j, const T& x) {
    for (++i; i < N; i += i & -i) (*bit[i]).add(j, x);
  }

  // i = [0, n), j = [0, m)
  T sum(int n, int m) const {
    if (n < 0 || m < 0) return T();
    T ret = T();
    for (; n; n -= n & -n) ret += (*bit[n]).sum(m);
    return ret;
  }

  // i = [nl, nr), j = [ml, mr)
  T sum(int nl, int ml, int nr, int mr) const {
    T ret = T();
    while (nl != nr) {
      if (nl < nr) {
        ret += (*bit[nr]).sum(ml, mr);
        nr -= nr & -nr;
      } else {
        ret -= (*bit[nl]).sum(ml, mr);
        nl -= nl & -nl;
      }
    }
    return ret;
  }
};

/*
 * @brief 動的二次元Binary Indexed Tree
 */

using ll = long long;
#define rep(i,a,b) for(ll i = (a); i < (b); i++)
#define rrep(i,a,b) for(ll i = (b)-1; i >= (a); i--)
#define all(a) (a).begin(), (a).end()

bool chmax(auto& a, auto b) {
    return a < b ? a = b, 1: 0;
}

vector<int> find_path(vector<int> a, vector<int> b) {
    int n = a.size();
    vector<int> rb(n);
    rep(i,0,n) rb[b[i]] = i;
    vector<int> path;

    int mx = -1;
    rrep(i,0,n) {
        if(chmax(mx, rb[a[i]])) {
            path.push_back(a[i]);
        }
    }

    return path;
}

void solve() {
    ll n,m;
    cin >> n >> m;
    vector<int> p(n), q(n), r(n);
    rep(i,0,n) {
        cin >> p[i];
        p[i]--;
    }
    rep(i,0,n) {
        cin >> q[i];
        q[i]--;
    }
    rep(i,0,n) {
        cin >> r[i];
        r[i]--;
    }
    vector<int> pq = find_path(p, q);
    vector<int> qr = find_path(q, r);
    vector<int> rp = find_path(r, p);

    // pq, qr, rp での辺が木になるかどうか
    set<int> V;
    set<pair<int,int>> E;
    rep(i,0,pq.size()) {
        V.insert(pq[i]);
        if(i) E.insert({min(pq[i-1], pq[i]), max(pq[i-1], pq[i])});
    }
    rep(i,0,qr.size()) {
        V.insert(qr[i]);
        if(i) E.insert({min(qr[i-1], qr[i]), max(qr[i-1], qr[i])});
    }
    rep(i,0,rp.size()) {
        V.insert(rp[i]);
        if(i) E.insert({min(rp[i-1], rp[i]), max(rp[i-1], rp[i])});
    }
    if(V.size() != E.size()+1) {
        cout << 0 << endl;
        return;
    }

    ll ans = 1;

    DynamicFenwickTree2D<int> BIT(n, n);
    vector<int> rq(n), rr(n);
    rep(i,0,n) {
        rq[q[i]] = i;
        rr[r[i]] = i;
    }

    rrep(i,0,n) {
        if(V.count(p[i]) == 0) {
            ans = ans * BIT.sum(rq[p[i]], rr[p[i]], n, n) % m;
        }
        BIT.add(rq[p[i]], rr[p[i]], 1);
    }

    cout << ans << endl;
}

int main() {
    int t;
    cin >> t;
    while(t--) solve();
}