Submission #1017792

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017792		lucri	September (APIO24_september)	C++17	100 / 100	299 ms	21964 KiB

september

#include <bits/stdc++.h>
std::vector<std::vector<int>>a;
int pozmin[100010],pozmax[100010],aint[400010];
void update(int poz,int b,int e,int pozu,int val)
{
    if(b>pozu||pozu>e)
        return;
    aint[poz]=std::max(aint[poz],val);
    if(b==e)
        return;
    update(poz*2,b,(b+e)/2,pozu,val);
    update(poz*2+1,(b+e)/2+1,e,pozu,val);
}
int maxim(int poz,int b,int e,int bi,int ei)
{
    if(b>ei||bi>e)
        return 0;
    if(bi<=b&&e<=ei)
        return aint[poz];
    return std::max(maxim(poz*2,b,(b+e)/2,bi,ei),
               maxim(poz*2+1,(b+e)/2+1,e,bi,ei));
}
int initializare(int nod,int &N)
{
    int p1=pozmin[nod],p2=pozmax[nod];
    for(auto x:a[nod])
        p2=std::max(p2,initializare(x,N));
    update(1,1,N,p1,p2);
    return p2;
}
int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S)
{
    a.clear();
    a.resize(N+5);
    for(int i=1;i<=4*N;++i)
        aint[i]=0;
    for(int i=1;i<N;++i)
    {
        a[F[i]].push_back(i);
        pozmin[i]=N;
        pozmax[i]=0;
    }
    for(int i=0;i<M;++i)
        for(int j=0;j<N-1;++j)
        {
            pozmin[S[i][j]]=std::min(pozmin[S[i][j]],j+1);
            pozmax[S[i][j]]=std::max(pozmax[S[i][j]],j+1);
        }
    initializare(0,N);
    int poz=1,ans=0;
    while(poz<N)
    {
        int bi=poz,ei=poz;
        while(maxim(1,1,N,bi,ei)!=ei)
            ei=maxim(1,1,N,bi,ei);
        poz=ei+1;
        ++ans;
    }
    return ans;
}

• 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