제출 #776358

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
776358		Tenis0206	서열 (APIO23_sequence)	C++17	41 / 100	2084 ms	53324 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

const int nmax = 5e5;

int n;
int v[nmax + 5];

vector<int> l[nmax + 5];

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

struct arbore_de_intervale
{
    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(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_int(ua,ub,val,nod*2,a,mij);
        }
        if(ub>mij)
        {
            update_int(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_de_intervale asp;

int sequence(int N, vector<int> A)
{
    n = N;
    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_int(i,n,+1,1,1,n);
    }
    int rez = 0;
    for(int val=1; val<=n; val++)
    {
        int nr = l[val].size();
        if(!nr)
        {
            continue;
        }
        for(auto it : l[val])
        {
            asp.update_int(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;
        }
        for(int i=0; i<=nr; i++)
        {
            for(int j=i+1; j<=nr; j++)
            {
                int cnt = j - i;
                if(dr[j] - st[i] >= -cnt && st[j] - dr[i] <= cnt)
                {
                    rez = max(rez, cnt);
                }
            }
        }
        for(auto it : l[val])
        {
            asp.update_int(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: 0 / 7
• Subtask 4: 0 / 12
• Subtask 5: 13 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18