Submission #1261443

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261443		nerrrmin	September (APIO24_september)	C++20	45 / 100	327 ms	26280 KiB

september

#include "september.h"

#include <vector>
#define pb push_back
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 10;
int n, m;
vector < int > g[maxn];
int tmr;
int pos[maxn];
int a[maxn], label[maxn];
int tin[maxn], tout[maxn];
void dfs(int beg, int from)
{
    tmr ++;
    a[tmr] = pos[beg];
    label[beg] = tmr;
    tin[beg] = tmr;
    for (auto nb: g[beg])
    {
        if(nb == beg)continue;
        dfs(nb, beg);
    }
    tout[beg] = tmr;
}

int t[maxn * 4];

void build(int i, int l, int r)
{
    if(l == r)
    {
        t[i] = a[l];
        return;
    }
    int mid = (l + r)/2;
    build(2*i, l, mid);
    build(2*i+1, mid+1, r);
    t[i] = max(t[2*i], t[2*i+1]);
}
int upos, uval;
void update(int i, int l, int r)
{
    if(l == r)
    {
        t[i] = uval;
        a[l] = uval;
        return;
    }
    int mid = (l + r)/2;
    if(upos <= mid)update(2*i, l, mid);
    else update(2*i+1, mid+1, r);
    t[i] = max(t[2*i], t[2*i+1]);
}
int ql, qr;
int query(int i, int l, int r)
{
    if(qr < l || ql > r)return 0;
    if(ql <= l && r <= qr)return t[i];
    int mid = (l + r)/2;
    return max(query(2*i, l, mid), query(2*i+1, mid+1, r));
}

int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S)
{

    n = N;
    m = M;
    for (int i = 0; i < n; ++ i)
        g[i].clear();
    for (int i = 0; i < n; ++ i)
    {
        int par = F[i];
        if(par != -1)g[par].pb(i);
    }
    for (int i = 0; i < m; ++ i)
    {
        for (int j = 0; j < n-1; ++ j)
        {
            int x = S[i][j];
            pos[x] = j;
        }
    }
    tmr = -1;
    dfs(0, -1);
    build(1, 1, tmr);
    int mx = 0;
    int day = 0;
    for (int d = 0; d < M; ++ d)
    {
        mx = 0;
        day = 0;
        int st = 0;
        vector < pair < int, int > > u;
        for (int i = 0; i < S[d].size(); ++ i)
        {
            int v = S[d][i];
            ql = tin[v];
            qr = tout[v];
            int nxt = query(1, 1, tmr);
            mx = max(mx, nxt);
            if(mx == i)
            {
                int rgl = st, rgr = i;
                u.pb(make_pair(st, i));

                day ++;
                mx = i + 1;
                st = i + 1;
            }
        }
        for(auto &[rgl, rgr]: u)
        {
            for (int k = rgr; k <= rgr; ++ k)
                {
                    upos = label[k];
                    uval = rgr;
                    update(1, 1, tmr);
                }
        }

    }
    return day;
}

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