Submission #776366

#	Time	Username	Problem	Language	Result	Execution time	Memory
776366		Tenis0206	Sequence (APIO23_sequence)	C++17	48 / 100	974 ms	122856 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

const int nmax = 5e5;

int dif;

int n;
int v[nmax + 5];

vector<int> l[nmax + 5];

int st[nmax + 5], dr[nmax + 5];

int pst[nmax + 5], pdr[nmax + 5];

struct arbore_lazy
{
    pair<int,int> ai[4 * nmax + 5];
    int lazy[4 * nmax + 5];
private:
    pair<int,int> Merge(pair<int,int> a, pair<int,int> b)
    {
        pair<int,int> rez;
        rez.first = min(a.first,b.first);
        rez.second = max(a.second,b.second);
        return rez;
    }
    void propag(int nod)
    {
        if(lazy[nod]==0)
        {
            return;
        }
        lazy[nod*2] += lazy[nod];
        lazy[nod*2+1] += lazy[nod];
        ai[nod*2].first += lazy[nod], ai[nod*2].second += lazy[nod];
        ai[nod*2+1].first += lazy[nod], ai[nod*2+1].second += lazy[nod];
        lazy[nod] = 0;
    }
public:
    void update(int ua, int ub, int val, int nod, int a, int b)
    {
        if(ua<=a && ub>=b)
        {
            ai[nod].first += val;
            ai[nod].second += val;
            lazy[nod] += val;
            return;
        }
        propag(nod);
        int mij = (a + b) >> 1;
        if(ua<=mij)
        {
            update(ua,ub,val,nod*2,a,mij);
        }
        if(ub>mij)
        {
            update(ua,ub,val,nod*2+1,mij+1,b);
        }
        ai[nod] = Merge(ai[nod*2],ai[nod*2+1]);
    }
    pair<int,int> query(int qa, int qb, int nod, int a, int b)
    {
        if(qa<=a && qb>=b)
        {
            return ai[nod];
        }
        propag(nod);
        int mij = (a + b) >> 1;
        if(qa<=mij && qb>mij)
        {
            return Merge(query(qa,qb,nod*2,a,mij),query(qa,qb,nod*2+1,mij+1,b));
        }
        if(qa<=mij)
        {
            return query(qa,qb,nod*2,a,mij);
        }
        return query(qa,qb,nod*2+1,mij+1,b);
    }
};

arbore_lazy asp;

struct arbore_de_intervale
{
    int ai[12 * nmax + 5];
    void update(int poz, int val, int nod, int a, int b, bool as = false)
    {
        if(a==b)
        {
            if(as)
            {
                ai[nod] = val;
            }
            ai[nod] = min(ai[nod],val);
            return;
        }
        int mij = (a + b) >> 1;
        if(poz<=mij)
        {
            update(poz,val,nod*2,a,mij,as);
        }
        else
        {
            update(poz,val,nod*2+1,mij+1,b,as);
        }
        ai[nod] = min(ai[nod*2],ai[nod*2+1]);
    }
    int query(int qa, int qb, int nod, int a, int b)
    {
        if(qa<=a && qb>=b)
        {
            return ai[nod];
        }
        int mij = (a + b) >> 1;
        if(qa<=mij && qb>mij)
        {
            return min(query(qa,qb,nod*2,a,mij),query(qa,qb,nod*2+1,mij+1,b));
        }
        if(qa<=mij)
        {
            return query(qa,qb,nod*2,a,mij);
        }
        return query(qa,qb,nod*2+1,mij+1,b);
    }
};

arbore_de_intervale aicnt;

int sequence(int N, vector<int> A)
{
    n = N;
    dif = 2 * n + 1;
    for(int i=1; i<=n; i++)
    {
        v[i] = A[i - 1];
        l[v[i]].push_back(i);
    }
    for(int i=1; i<=n; i++)
    {
        asp.update(i,n,+1,1,1,n);
    }
    int rez = 0;
    for(int i=1;i<=n+dif;i++)
    {
        aicnt.update(i,nmax,1,1,n+dif,1);
    }
    for(int val=1; val<=n; val++)
    {
        int nr = l[val].size();
        if(!nr)
        {
            continue;
        }
        for(auto it : l[val])
        {
            asp.update(it,n,-1,1,1,n);
        }
        if(l[val].front() != 1)
        {
            pair<int,int> sp = asp.query(1,l[val].front()-1,1,1,n);
            st[0] = sp.first;
            dr[0] = sp.second;
            st[0] = min(st[0], 0);
            dr[0] = max(dr[0], 0);
        }
        else
        {
            st[0] = 0;
            dr[0] = 0;
        }
        for(int i=0; i<nr; i++)
        {
            int u = n;
            if(i + 1 < nr)
            {
                u = l[val][i + 1] - 1;
            }
            pair<int,int> sp = asp.query(l[val][i],u,1,1,n);
            st[i + 1] = sp.first;
            dr[i + 1] = sp.second;
        }
        auto cmpst = [](int a, int b)
        {
            return (a + st[a] <= b + st[b]);
        };
        auto cmpdr = [](int a, int b)
        {
            return (a + dr[a] <= b + dr[b]);
        };
        for(int i=0;i<=nr;i++)
        {
            pst[i] = i, pdr[i] = i;
        }
        sort(pst,pst+nr+1,cmpst);
        sort(pdr,pdr+nr+1,cmpdr);
        int poz = 0;
        for(int p=0;p<=nr;p++)
        {
            int j = pdr[p];
            while(poz <= nr && pst[poz] + st[pst[poz]] <= dr[j] + j)
            {
                int i = pst[poz];
                aicnt.update(dr[i]-i+dif,i,1,1,n+dif);
                ++poz;
            }
            rez = max(rez, j - aicnt.query(st[j]-j+dif,n+dif,1,1,n+dif));
        }
        for(int i=0;i<=nr;i++)
        {
            aicnt.update(dr[i]-i+dif,nmax,1,1,n+dif,1);
        }
        for(auto it : l[val])
        {
            asp.update(it,n,-1,1,1,n);
        }
    }
    return rez;
}

#ifdef home

int main()
{
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
    int nn;
    cin>>nn;
    vector<int> vv(nn);
    for(int i=1; i<=nn; i++)
    {
        cin>>vv[i - 1];
    }
    cout<<sequence(nn,vv)<<'\n';
    return 0;
}

#endif // home

• Subtask 1: 11 / 11
• Subtask 2: 17 / 17
• Subtask 3: 7 / 7
• Subtask 4: 0 / 12
• Subtask 5: 13 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18