Submission #757804

#	Time	Username	Problem	Language	Result	Execution time	Memory
757804		Andrei	Sequence (APIO23_sequence)	C++17	24 / 100	2084 ms	47872 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

int fr[500005];

vector <int> pos[500005];

/**
1 <= l <= pos[i][j]
pos[i][j+x-1] + 1 <= r <= n

0000000****111

abs(cnt[-1]-cnt[1]) <= x
abs(cnt[1]-cnt[-1]) <= x
abs(pref[r] - pref[l]) <= x

-x <= pref[r] - pref[l] <= x
pref[l] - pref[r] <= x sau pref[r] - pref[l] <= x

[a,b]
[c,d]

[a-x,b+x] trebuie sa se intersecteze cu [c,d]
*/

struct LazySegmentTree
{
    int n;
    int aux[500005];
    int minim[2000005];
    int maxim[2000005];
    int lazy[2000005];

    void build(int i,int x,int y)
    {
        lazy[i]=0;
        if(x==y)
            minim[i]=maxim[i]=aux[x];
        else
        {
            int mid=(x+y)/2;
            build(2*i,x,mid);
            build(2*i+1,mid+1,y);
            minim[i]=min(minim[2*i],minim[2*i+1]);
            maxim[i]=max(maxim[2*i],maxim[2*i+1]);
        }
    }

    void init(int _n)
    {
        n=_n;
        for(int i=0; i<=n; i++)
            aux[i]=i;
        build(1,0,n);
    }

    void propag(int i,int x,int y)
    {
        if(x!=y)
        {
            lazy[2*i]+=lazy[i];
            lazy[2*i+1]+=lazy[i];
            minim[2*i]+=lazy[i];
            maxim[2*i]+=lazy[i];
            minim[2*i+1]+=lazy[i];
            maxim[2*i+1]+=lazy[i];
            lazy[i]=0;
        }
    }

    void update(int i,int x,int y,int l,int r,int v)
    {
        propag(i,x,y);
        if(l<=x && y<=r)
        {
            lazy[i]+=v;
            minim[i]+=v;
            maxim[i]+=v;
            propag(i,x,y);
        }
        else
        {
            int mid=(x+y)/2;
            if(l<=mid)
                update(2*i,x,mid,l,r,v);
            if(r>mid)
                update(2*i+1,mid+1,y,l,r,v);

            minim[i]=min(minim[2*i],minim[2*i+1]);
            maxim[i]=max(maxim[2*i],maxim[2*i+1]);
        }
    }

    pair <int,int> query(int i,int x,int y,int l,int r)
    {
        propag(i,x,y);
        if(l<=x && y<=r)
            return make_pair(minim[i],maxim[i]);

        int mid=(x+y)/2;
        pair <int,int> aux=make_pair(n,-n);
        if(l<=mid)
            aux=query(2*i,x,mid,l,r);
        if(r>mid)
        {
            pair <int,int> temp;
            temp=query(2*i+1,mid+1,y,l,r);

            aux.first=min(aux.first,temp.first);
            aux.second=max(aux.second,temp.second);
        }
        return aux;
    }
} sgt;

bool ok(int n,int x)
{
    sgt.init(n);
    for(int i=1; i<=n; i++)
    {
        for(auto it:pos[i])
            sgt.update(1,0,n,it+1,n,-1);

        if(fr[i]>=x)
        {
            for(int j=0; j+x-1<fr[i]; j++)
            {
                pair <int,int> aux=sgt.query(1,0,n,0,pos[i][j]);
                int a=aux.first;
                int b=aux.second;

                aux=sgt.query(1,0,n,pos[i][j+x-1]+1,n);
                int c=aux.first;
                int d=aux.second;

                if(max(a-x,c)<=min(b+x,d))
                    return 1;
            }
        }
        for(auto it:pos[i])
            sgt.update(1,0,n,it+1,n,-1);
    }
    return 0;
}

int sequence(int n,vector <int> a)
{
    int mxfr=0;
    for(int i=0; i<n; i++)
    {
        fr[a[i]]++;
        mxfr=max(mxfr,fr[a[i]]);
        pos[a[i]].push_back(i);
    }

    int st=1,dr=mxfr,mij;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(ok(n,mij)==1)
            st=mij+1;
        else
            dr=mij-1;
    }
    return st-1;
}

/*
int n;

vector <int> a;

int main()
{
    cin>>n;
    for(int i=0; i<n; i++)
    {
        int x;
        cin>>x;
        a.push_back(x);
    }
    cout<<sequence(n,a)<<"\n";
    return 0;
}
*/

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