Submission #1109582

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109582		Pioneer	Sequence (APIO23_sequence)	C++17	0 / 100	2051 ms	82688 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define sz(s) ((int)s.size())
#define pii pair<int,int>
#define F first
#define S second

const int MAX=5e5+10;
const int inf=1e9;

struct segtree{
    int mx[4*MAX],mn[4*MAX],add[4*MAX];

    void init(){
        memset(mx,0,sizeof(mx));
        memset(mn,0,sizeof(mn));
        memset(add,0,sizeof(add));
    }

    void upd(int v,int x){
        mx[v]+=x;
        mn[v]+=x;
        add[v]+=x;
    }

    void push(int v){
        if(add[v]){
            upd(2*v,add[v]);
            upd(2*v+1,add[v]);
            add[v]=0;
        }
    }

    void update(int v,int tl,int tr,int l,int r,int x){
        if(l>r||tl>r||l>tr)return;
        if(l<=tl&&tr<=r){
            upd(v,x);
            return;
        }
        push(v);
        int tm=(tl+tr)/2;
        update(2*v,tl,tm,l,r,x);
        update(2*v+1,tm+1,tr,l,r,x);
        mx[v]=max(mx[2*v],mx[2*v+1]);
        mn[v]=min(mn[2*v],mn[2*v+1]);
    }

    pii get(int v,int tl,int tr,int l,int r){
        if(l>r||tl>r||l>tr)return {inf,-inf};
        if(l<=tl&&tr<=r)return {mn[v],mx[v]};
        int tm=(tl+tr)/2;
        pii a=get(2*v,tl,tm,l,r),b=get(2*v+1,tm+1,tr,l,r);
        return {min(a.F,b.F),max(a.S,b.S)};
    }
}t[2];

int n;
vector<int> pos[MAX];

bool check(int mid){
    t[0].init();
    t[1].init();
    for(int i=1;i<=n;i++){
        t[0].update(1,0,n,i,n,1);
        t[1].update(1,0,n,i,n,1);
    }
    for(int i=1;i<=n;i++){
        for(int r=sz(pos[i])-1;r>=1;r--){
            int l=r-mid+1;
            if(l>=1){
                int mxR=t[0].get(1,0,n,pos[i][r],n).S;
                int mnR=t[1].get(1,0,n,pos[i][r],n).F-2*mid;
                int mxL=t[0].get(1,0,n,pos[i][l-1],pos[i][l]-1).S;
                int mnL=t[1].get(1,0,n,pos[i][l-1],pos[i][l]-1).F;
                // cout<<pos[i][l]<<" "<<pos[i][r]<<" "<<mnL<<" "<<mxL<<" "<<mnR<<" "<<mxR<<"\n";
                if(max(mnL,mnR)<=min(mxL,mxR))return 1;
            }
            t[1].update(1,0,n,pos[i][r],n,-2);
        }
        for(int r=1;r<sz(pos[i]);r++){
            t[0].update(1,0,n,pos[i][r],n,-2);
        }
    }
    return 0;
}

int sequence(int N,vector<int> a){
    n=N;
    for(int i=1;i<=n;i++)pos[i].pb(0);
    for(int i=0;i<n;i++){
        pos[a[i]].pb(i+1);
    }
    int l=2,r=n,res=1;
    while(l<=r){
        int m=(l+r)/2;
        if(check(m)){
            l=m+1;
            res=m;
        }
        else r=m-1;
    }
    // check(3);
    return res;
}

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