Submission #1109602

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109602		Pioneer	Sequence (APIO23_sequence)	C++17	100 / 100	798 ms	84152 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]};
        push(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];
 
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 res=1;
    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 l=sz(pos[i])-1;l>=1;l--){
            int r=l+res;
            t[1].update(1,0,n,pos[i][l],n,-2);
            while(r<sz(pos[i])){
                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;
                int mxL=t[0].get(1,0,n,pos[i][l-1],pos[i][l]-1).S;
                int mnL=t[0].get(1,0,n,pos[i][l-1],pos[i][l]-1).F;
                // cout<<i<<" "<<pos[i][r]<<" "<<n<<" "<<mnL<<" "<<mxL<<" "<<mnR<<" "<<mxR<<"\n";
                if(max(mnL,mnR)<=min(mxL,mxR))r++,res++;
                else break;
            }
        }
        for(int r=1;r<sz(pos[i]);r++){
            t[0].update(1,0,n,pos[i][r],n,-2);
        }
    }
    return res;
}

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