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

• 問題: No.3748 Three Pruning Order
• ユーザー: Naru820
• 提出日時: 2026-09-18 21:34:16
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 5,537 bytes
• コンパイル時間: 1,055 ms
• コンパイル使用メモリ: 174,492 KB
• 実行使用メモリ: 10,368 KB
• 最終ジャッジ日時: 2026-09-25 20:56:20
• 合計ジャッジ時間: 12,190 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

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

ソースコード

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

using namespace std;

const int MAXN = 100005;

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

int N;
long long M;
int P_arr[MAXN], Q_arr[MAXN], R_arr[MAXN];
int posP[MAXN], posQ[MAXN], posR[MAXN];
Point pts[MAXN], temp_pts[MAXN];
int D_arr[MAXN];
int bit_tree[MAXN];

// BIT の操作（グローバル配列で高速化）
inline void bit_add(int i, int val) {
    for (; i <= N; i += i & -i) bit_tree[i] += val;
}

inline int bit_query(int i) {
    int sum = 0;
    for (; i > 0; i -= i & -i) sum += bit_tree[i];
    return sum;
}

inline void bit_clear(int i) {
    for (; i <= N; i += i & -i) {
        if (bit_tree[i] == 0) break;
        bit_tree[i] = 0;
    }
}

// CDQ分割統治（動的確保なし）
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, k = L;
    while (i <= mid && j <= R) {
        if (pts[i].q > pts[j].q) {
            bit_add(pts[i].r, 1);
            temp_pts[k++] = pts[i++];
        } else {
            D_arr[pts[j].id] += bit_query(N) - bit_query(pts[j].r);
            temp_pts[k++] = pts[j++];
        }
    }
    while (i <= mid) {
        bit_add(pts[i].r, 1);
        temp_pts[k++] = pts[i++];
    }
    while (j <= R) {
        D_arr[pts[j].id] += bit_query(N) - bit_query(pts[j].r);
        temp_pts[k++] = pts[j++];
    }
    
    for (int p = L; p <= mid; p++) bit_clear(pts[p].r);
    for (int p = L; p <= R; p++) pts[p] = temp_pts[p];
}

int V0[MAXN];
int v0_idx[MAXN];
int best_target[MAXN][3]; // 各タイプ(0,1,2)で最も近い親候補

int out_node[MAXN];
int out_color[MAXN];
bool vis[MAXN];
int K_cnt;
int n0;
int p_n_idx, q_n_idx, r_n_idx;

bool 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;

    for (int i = 0; i < n0; i++) vis[i] = 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_idx, 0) || !trace(q_n_idx, 1) || !trace(r_n_idx, 2)) return false;
    if (!vis[root]) { vis[root] = true; visited_count++; }

    return visited_count == n0;
}

void dfs(int idx, bool has_root) {
    if (idx == n0) {
        if (has_root && check_tree()) K_cnt++;
        return;
    }

    if (!has_root) {
        out_node[idx] = -1;
        out_color[idx] = -1;
        dfs(idx + 1, true);
    }

    for (int c = 0; c < 3; c++) {
        int v = best_target[idx][c];
        if (v != -1) {
            out_node[idx] = v;
            out_color[idx] = c;
            dfs(idx + 1, has_root);
        }
    }
}

void solve() {
    cin >> N >> M;
    for (int i = 1; i <= N; i++) { cin >> P_arr[i]; posP[P_arr[i]] = i; }
    for (int i = 1; i <= N; i++) { cin >> Q_arr[i]; posQ[Q_arr[i]] = i; }
    for (int i = 1; i <= N; i++) { cin >> R_arr[i]; posR[R_arr[i]] = i; }

    for (int i = 1; i <= N; i++) {
        pts[i] = {posP[i], posQ[i], posR[i], i};
        D_arr[i] = 0;
        v0_idx[i] = -1;
    }

    sort(pts + 1, pts + N + 1, [](const Point& a, const Point& b) {
        return a.p > b.p;
    });

    cdq(1, N);

    n0 = 0;
    long long ways = 1;
    for (int i = 1; i <= N; i++) {
        if (D_arr[i] == 0) {
            v0_idx[i] = n0;
            V0[n0++] = i;
        } else {
            ways = (ways * D_arr[i]) % M;
        }
    }

    if (n0 == 0) {
        cout << 0 << "\n";
        return;
    }

    int PN = P_arr[N], QN = Q_arr[N], RN = R_arr[N];
    p_n_idx = v0_idx[PN];
    q_n_idx = v0_idx[QN];
    r_n_idx = v0_idx[RN];

    if (p_n_idx == -1 || q_n_idx == -1 || r_n_idx == -1) {
        cout << 0 << "\n";
        return;
    }

    // 各頂点から各タイプへの親候補を「最も近い1点」に絞り込む
    for (int i = 0; i < n0; i++) {
        for (int c = 0; c < 3; c++) best_target[i][c] = -1;
        int u = V0[i];

        int min_pos[3] = {1000000, 1000000, 1000000};

        for (int j = 0; j < n0; j++) {
            if (i == j) continue;
            int v = V0[j];
            bool pq = (posP[u] < posP[v]);
            bool qq = (posQ[u] < posQ[v]);
            bool rq = (posR[u] < posR[v]);

            // タイプ0: Pでv<u, Q,Rでu<v
            if (!pq && qq && rq) {
                if (posQ[v] < min_pos[0]) {
                    min_pos[0] = posQ[v];
                    best_target[i][0] = j;
                }
            }
            // タイプ1: Qでv<u, P,Rでu<v
            if (pq && !qq && rq) {
                if (posR[v] < min_pos[1]) {
                    min_pos[1] = posR[v];
                    best_target[i][1] = j;
                }
            }
            // タイプ2: Rでv<u, P,Qでu<v
            if (pq && qq && !rq) {
                if (posP[v] < min_pos[2]) {
                    min_pos[2] = posP[2];
                    best_target[i][2] = j;
                }
            }
        }
    }

    K_cnt = 0;
    dfs(0, false);

    cout << (ways * K_cnt) % M << "\n";
}

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