제출 #1293520

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1293520		sh1ka	9월 (APIO24_september)	C++20	큐에 대기중	0 ms	0 KiB

september

#include "september.h"
#include <bits/stdc++.h>
using namespace std;
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2")



int solve(int n, int m, std::vector<int> f, std::vector<std::vector<int>> s) {
    #define int int64_t

    vector<int> id(n), sosal(n, -1);
    for (int i = 0; i < n - 1; i++)
        id[s[0][i]] = i;
    
    for (int i = 1; i < n; i++) {
        sosal[f[i]] = max(sosal[f[i]], id[i] + 1);
    }

    const int INF = 1e12;

    vector<int> mxx(n);

    for (int i = 0; i + 1 < n; i++)
        mxx[i + 1] = sosal[s[0][i]];
    for (int i = 1; i < n; i++)
        mxx[i] = max(mxx[i], mxx[i - 1]);

    mt19937 rnd(1488);
    vector<int> hsh(n);
    for (int i = 1; i < n; i++)
        hsh[i] = rnd();

    vector<int> ph1(n), penis(n);
    
    for (int i = 0; i + 1 < n; i++) {
        int cur_val = 0;
        for (int j = 0; j < m; j++)
            cur_val += hsh[s[j][i]];
        ph1[i + 1] = cur_val + ph1[i];    
    
        cur_val = 0;
        for (int j = 0; j < m; j++)
            cur_val += hsh[s[0][i]];
        penis[i + 1] = cur_val + penis[i];
    }

    vector<int> dp(n, -INF);
    dp[0] = 0;

    vector<int> fenw(n + 10, -INF);

    auto upd = [&](int id, int x) {
        id += 1;
        for (; id < n + 10; id += id & -id)
            fenw[id] = max(fenw[id], x);
    };

    auto get = [&](int r) -> int {
        int res = -INF;
        for (; r > 0; r -= r & -r)
            res = max(res, fenw[r]);
        return res;
    };

    upd(0, 0);

    for (int i = 1; i < n; i++) {
        if (ph1[i] != penis[i])
            continue;
        if (mxx[i] > i)
            continue;
        
        int val = get(i) + 1;
        dp[i] = val;
        upd(i, val);

        // for (int j = 0; j < i; j++) {
        //     dp[i] = max(dp[i], dp[j] + 1);
        // }
    }

    return dp[n - 1];
}

// int32_t main() {
//     using namespace std;
//     int t; cin >> t;
//     int n, m; cin >> n >> m;
//     vector<int32_t> f(n - 1);
//     vector<vector<int32_t>> s(m, vector<int32_t>(n - 1));
//     for (int32_t &i : f)
//         cin >> i;
//     for (auto &i : s)
//         for (auto &j : i)
//             cin >> j;
//     cout << solve(n, m, f, s);
// }