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

• 問題: No.3748 Three Pruning Order
• ユーザー: Naru820
• 提出日時: 2026-09-18 10:52:10
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 5,046 bytes
• コンパイル時間: 1,506 ms
• コンパイル使用メモリ: 195,556 KB
• 実行使用メモリ: 9,816 KB
• 最終ジャッジ日時: 2026-09-25 20:56:14
• 合計ジャッジ時間: 12,703 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge2_1

ファイルパターン	結果
sample	-- * 1
other	TLE * 1 -- * 41

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Point {
    int p, q, r, id;
};

// CDQ分割用のBIT
struct BIT {
    int n;
    vector<int> tree;
    BIT(int n) : n(n), tree(n + 1, 0) {}
    void add(int i, int val) {
        for (; i <= n; i += i & -i) tree[i] += val;
    }
    int query(int i) {
        int sum = 0;
        for (; i > 0; i -= i & -i) sum += tree[i];
        return sum;
    }
    void clear(int i) {
        for (; i <= n; i += i & -i) {
            if (tree[i] == 0) break;
            tree[i] = 0;
        }
    }
};

int N;
long long M;
vector<int> D;
vector<Point> pts;
BIT* bit;

void cdq(int L, int R) {
    if (L >= R) return;
    int mid = L + (R - L) / 2;
    cdq(L, mid);
    cdq(mid + 1, R);
    
    int i = L, j = mid + 1;
    vector<Point> temp;
    temp.reserve(R - L + 1);
    
    while (i <= mid && j <= R) {
        if (pts[i].q > pts[j].q) {
            bit->add(pts[i].r, 1);
            temp.push_back(pts[i++]);
        } else {
            D[pts[j].id] += bit->query(N) - bit->query(pts[j].r);
            temp.push_back(pts[j++]);
        }
    }
    while (i <= mid) {
        bit->add(pts[i].r, 1);
        temp.push_back(pts[i++]);
    }
    while (j <= R) {
        D[pts[j].id] += bit->query(N) - bit->query(pts[j].r);
        temp.push_back(pts[j++]);
    }
    
    for (int k = L; k <= mid; k++) bit->clear(pts[k].r);
    for (int k = 0; k < temp.size(); k++) pts[L + k] = temp[k];
}

void solve() {
    cin >> N >> M;
    vector<int> P(N + 1), Q(N + 1), R(N + 1);
    vector<int> posP(N + 1), posQ(N + 1), posR(N + 1);
    
    for (int i = 1; i <= N; i++) { cin >> P[i]; posP[P[i]] = i; }
    for (int i = 1; i <= N; i++) { cin >> Q[i]; posQ[Q[i]] = i; }
    for (int i = 1; i <= N; i++) { cin >> R[i]; posR[R[i]] = i; }
    
    pts.assign(N + 1, {0, 0, 0, 0});
    for (int i = 1; i <= N; i++) {
        pts[i] = {posP[i], posQ[i], posR[i], i};
    }
    
    sort(pts.begin() + 1, pts.end(), [](const Point& a, const Point& b) {
        return a.p > b.p;
    });
    
    D.assign(N + 1, 0);
    bit = new BIT(N);
    cdq(1, N);
    delete bit;
    
    vector<int> V0;
    long long ways = 1;
    for (int i = 1; i <= N; i++) {
        if (D[i] == 0) V0.push_back(i);
        else ways = (ways * D[i]) % M;
    }
    
    int n0 = V0.size();
    if (n0 == 0) {
        cout << 0 << "\n";
        return;
    }
    
    vector<vector<vector<int>>> edges(n0, vector<vector<int>>(3));
    for (int i = 0; i < n0; i++) {
        for (int j = 0; j < n0; j++) {
            if (i == j) continue;
            int u = V0[i], v = V0[j];
            bool pq = (posP[u] < posP[v]);
            bool qq = (posQ[u] < posQ[v]);
            bool rq = (posR[u] < posR[v]);
            
            if (!pq && qq && rq) edges[i][0].push_back(j);
            if (pq && !qq && rq) edges[i][1].push_back(j);
            if (pq && qq && !rq) edges[i][2].push_back(j);
        }
    }
    
    int PN = P[N], QN = Q[N], RN = R[N];
    int p_n = -1, q_n = -1, r_n = -1;
    for (int i = 0; i < n0; i++) {
        if (V0[i] == PN) p_n = i;
        if (V0[i] == QN) q_n = i;
        if (V0[i] == RN) r_n = i;
    }
    
    if (p_n == -1 || q_n == -1 || r_n == -1) {
        cout << 0 << "\n";
        return;
    }
    
    int K = 0;
    vector<int> out_node(n0, -1);
    vector<int> out_color(n0, -1);
    
    auto check_tree = [&]() {
        int root = -1;
        for (int i = 0; i < n0; i++) {
            if (out_node[i] == -1) {
                if (root != -1) return false;
                root = i;
            }
        }
        if (root == -1) return false;
        
        vector<bool> vis(n0, false);
        int visited_count = 0;
        
        auto trace = [&](int start, int color) {
            int curr = start;
            while (curr != root) {
                if (vis[curr]) return false;
                vis[curr] = true;
                visited_count++;
                if (out_color[curr] != color) return false;
                curr = out_node[curr];
            }
            return true;
        };
        
        if (!trace(p_n, 0) || !trace(q_n, 1) || !trace(r_n, 2)) return false;
        if (!vis[root]) { vis[root] = true; visited_count++; }
        
        return visited_count == n0;
    };
    
    auto dfs = [&](auto& self, int idx, bool has_root) -> void {
        if (idx == n0) {
            if (has_root && check_tree()) K++;
            return;
        }
        if (!has_root) {
            out_node[idx] = -1; out_color[idx] = -1;
            self(self, idx + 1, true);
        }
        for (int c = 0; c < 3; c++) {
            for (int v : edges[idx][c]) {
                out_node[idx] = v; out_color[idx] = c;
                self(self, idx + 1, has_root);
            }
        }
    };
    
    dfs(dfs, 0, false);
    cout << (ways * K) % M << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int T;
    if (cin >> T) {
        while (T--) solve();
    }
    return 0;
}