Submission #992009

#	Time	Username	Problem	Language	Result	Execution time	Memory
992009		12345678	September (APIO24_september)	C++17	100 / 100	397 ms	25820 KiB

september

#include "september.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5;

int in[nx], out[nx], t, n, st, rv[nx], cnt;
vector<int> d[nx], k;

struct segtree
{
    int d[4*nx];
    void build(int l, int r, int i)
    {
        d[i]=0;
        if (l==r) return;
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
    }
    void update(int l, int r, int i, int idx, int vl)
    {
        if (idx<l||r<idx) return;
        if (l==r) return d[i]=max(d[i], vl), void();
        int md=(l+r)/2;
        update(l ,md, 2*i, idx ,vl);
        update(md+1, r, 2*i+1, idx, vl);
        d[i]=max(d[2*i], d[2*i+1]);
    }
    int query(int l, int r, int i, int ql, int qr)
    {
        if (qr<l||r<ql) return 0;
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return max(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
    }
} s, mxseg;

struct mnsegtree
{
    int d[4*nx];
    void build(int l, int r, int i)
    {
        d[i]=1e9;
        if (l==r) return;
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
    }
    void update(int l, int r, int i, int idx, int vl)
    {
        if (idx<l||r<idx) return;
        if (l==r) return d[i]=min(d[i], vl), void();
        int md=(l+r)/2;
        update(l ,md, 2*i, idx ,vl);
        update(md+1, r, 2*i+1, idx, vl);
        d[i]=min(d[2*i], d[2*i+1]);
    }
    int query(int l, int r, int i, int ql, int qr)
    {
        if (qr<l||r<ql) return 0;
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return min(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
    }
} mnseg;

void dfs(int u, int p)
{
    in[u]=++t;
    //cout<<"update "<<u<<' '<<t<<' '<<rv[u]<<'\n';
    if (u!=0) s.update(1, n, 1, t, rv[u]);
    for (auto v:d[u]) dfs(v, u);
    out[u]=t;
}

int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
    for (int i=0; i<N-1; i++) rv[S[0][i]]=i;
    n=N, t=0, st=0, cnt=0;
    int res=0;
    for (int i=0; i<N; i++) in[i]=out[i]=0, d[i].clear();
    for (int i=1; i<N; i++) d[F[i]].push_back(i);
    s.build(1, N, 1);
    mxseg.build(0, N-2, 1);
    mnseg.build(0, N-2, 1);
    for (int i=0; i<N-1; i++) mxseg.update(0, N-2, 1, i, i);
    for (int i=0; i<N-1; i++) mnseg.update(0, N-2, 1, i, i);
    for (int i=1; i<M; i++)
    {
        for (int j=0; j<N-1; j++)
        {
            mxseg.update(0, N-2, 1, rv[S[i][j]], j);
            mnseg.update(0, N-2, 1, rv[S[i][j]], j);
        }
    }
    dfs(0, 0);
    while (st<N-1)
    {
        int mx=0;
        for (int lst=st; lst<N-1; lst++)
        {
            mx=max(mx, s.query(1, n, 1, in[S[0][lst]], out[S[0][lst]]));
            //cout<<"debug "<<st<<' '<<lst<<' '<<mx<<' '<<S[0][lst]<<'\n';
            if (mxseg.query(0, N-2, 1, st, lst)>lst) continue;
            if (mx==lst) 
            {
                res++;
                st=lst+1;
                break;
            }
        }
    }
    return res;
}

• 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