제출 #1166488

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166488		Sang	9월 (APIO24_september)	C++20	100 / 100	295 ms	23104 KiB

september

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

#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define task "kbsiudthw"

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;

const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 2277;

struct IT{
    int n;
    vi T;

    IT () {};
    IT(int _n){
        int k = 1;
        n = _n;
        while (2 * k <= n) k *= 2;
        T.resize(4 * k, 0);
    }

    void update(int id, int l, int r, int pos, int val){
        if(l == r){
            T[id] = val;
            return;
        }
        int m = (l + r)/2;
        if (pos <= m) update(id*2, l, m, pos, val);
        else update(id*2+1, m+1, r, pos, val);
        T[id] = max(T[id*2], T[id*2+1]);
    }

    int get(int id, int l, int r, int u, int v){
        if (l > v || r < u) return 0;
        if (u <= l && r <= v) return T[id];
        int m = (l + r)/2;
        return max(get(id*2, l, m, u, v), get(id*2+1, m+1, r, u, v));
    }
};

mt19937 rd(time(0));

int Rand(int l, int r){
    return l + (rd()%(r - l + 1) + r - l + 1) %(r - l + 1);
}

int n, m, in[N], ou[N], timer, v[N];
vector<int> G[N];

void dfs(int u, int par){
    in[u] = ++timer;
    for (int &v : G[u]){
        if(v == par) continue;
        dfs(v, u);
    }
    ou[u] = timer;
}

int solve(int _n, int _m, vector<int> F, vector<vi> S){
    n = _n; m = _m;
    FOR (i, 1, n - 1){
        G[i].pb(F[i]);
        G[F[i]].pb(i);
    }
    dfs(0, -1);
    vector<IT> seg(m);
    vector<int> pos(n, 0);
    FOR (i, 0, m - 1) {
        seg[i] = IT(n);
        FOR (j, 0, n - 2){
            pos[S[i][j]] = max(pos[S[i][j]], j);
            seg[i].update(1, 1, n, in[S[i][j]], j);
        }
    }
    int last = -1;
    vector<ii> a;
    FOR (i, 0, n - 2){
        int mx = 0;
        FOR (j, 0, m - 1){
            mx = max(mx, seg[j].get(1, 1, n, in[S[j][i]], ou[S[j][i]]));
            mx = max(mx, pos[S[j][i]]);
        }
        if (last < i){
            a.pb({i, mx});
        } else {
            assert(a.size());
            a.back().se = max(last, mx);
        }
        last = max(last, mx);
    }
//    FOR (i, 0, n - 1) v[i] = Rand(0, 1e9);
//    vector<vector<long long>> pref(m, vector<long long>(n, 0));
//    vector<vector<long long>> arr(m, vector<long long>(n, 0));
//    FOR (i, 0, m - 1){
//        pref[i][0] = v[S[i][0]];
//        FOR (j, 1, n - 2) pref[i][j] = pref[i][j-1] + v[S[i][j]];
//        FOR (j, 0, (int)a.size() - 1){
//            arr[i][j] = pref[i][a[j].se] - pref[i][a[j].fi] + v[S[i][a[j].fi]];
//        }
//    }

    FOR (i, 0, n - 1){
        G[i].clear();
        in[i] = ou[i] = 0;
    }
    timer = 0;
    return a.size();
//    vector<int> dp(a.size() + 2, 0);
//    dp[0] = 0;
//    FOR (i, 1, (int)a.size()){
//        vector<int> s(m);
//        FORD(j, i, 1){
//            FOR (z, 0, m - 1) s[z] += arr[z][j - 1];
//            int ok = 1;
//            FOR (i, 0, m - 2) if (s[i] != s[i+1]) ok = 0;
//            if (ok) dp[i] = max(dp[i], dp[j-1] +1 );
//        }
//    }
//    FOR (i, 0, n - 1){
//        G[i].clear();
//        in[i] = ou[i] = 0;
//    }
//    timer = 0;
//
//    return dp[a.size()];
}


#ifdef _Pbrngw_
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    cout << solve(5, 2, {-1, 0, 0, 1, 1}, {{1, 2, 3, 4}, {4, 1, 2, 3}}) << '\n';
    cout << solve(3, 1, {-1, 0, 0 }, {{2, 3}}) << '\n';

    return 0;
}
#endif // _Pbrngw_

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 5 / 5
• Subtask 4: 9 / 9
• Subtask 5: 5 / 5
• Subtask 6: 11 / 11
• Subtask 7: 9 / 9
• Subtask 8: 11 / 11
• Subtask 9: 9 / 9
• Subtask 10: 16 / 16