제출 #1273205

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273205		imarn	서열 (APIO23_sequence)	C++20	69 / 100	2047 ms	170004 KiB

sequence

//#include "festival.h"
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#define ll long long
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define ub(x,i) upper_bound(all(x),i)-x.begin()
#define lb(x,i) lower_bound(all(x),i)-x.begin()
#define sz(x) (ll)x.size()
#define cd complex<double>
#define t3 tuple<int,int,int>
using namespace std;
const int mxn=5e5+5;
const ll inf=1e16;
vector<int>g[mxn];
int a[mxn];
struct lazy{
    int t[8*mxn]{0},lz[8*mxn]{0};
    void push(int i,int l,int r){
        t[i]+=lz[i];
        if(l<r)lz[2*i]+=lz[i],lz[2*i+1]+=lz[i];
        lz[i]=0;
    }
    void update(int i,int l,int r,int tl,int tr,int v){
        push(i,l,r);
        if(r<tl||l>tr)return;
        if(r<=tr&&l>=tl){
            lz[i]+=v;push(i,l,r);return;
        }int m=(l+r)>>1;
        update(2*i,l,m,tl,tr,v);update(2*i+1,m+1,r,tl,tr,v);
        t[i]=max(t[2*i],t[2*i+1]);
    }
    int qr(int i,int l,int r,int tl,int tr){
        push(i,l,r);
        if(r<tl||l>tr)return -1e9;
        if(r<=tr&&l>=tl)return t[i];
        int m=(l+r)>>1;
        return max(qr(2*i,l,m,tl,tr),qr(2*i+1,m+1,r,tl,tr));
    }
}sg[2];
struct lazy2{
    int t[8*mxn]{0},lz[4*mxn]{0},lz2[8*mxn]{0};
    void push2(int i,int l,int r){
        if(lz2[i]==0)return;
        t[i]=lz2[i],lz[i]=lz2[i];
        if(l<r)lz2[2*i]=lz2[i],lz2[2*i+1]=lz2[i];
        lz2[i]=0;
    }
    void push(int i,int l,int r){
        push2(i,l,r);
        t[i]=min(t[i],lz[i]);
        if(l<r){
            int m=(l+r)>>1;
            push2(2*i,l,m);
            push2(2*i+1,m+1,r);
            lz[2*i]=min(lz[i],lz[2*i]);lz[2*i+1]=min(lz[i],lz[2*i+1]);
        }lz[i]=1e9;
    }
    void update(int i,int l,int r,int tl,int tr,int v){
        push(i,l,r);
        if(r<tl||l>tr)return;
        if(r<=tr&&l>=tl){
            lz[i]=v;
            push(i,l,r);
            return;
        }int m=(l+r)>>1;
        update(2*i,l,m,tl,tr,v);update(2*i+1,m+1,r,tl,tr,v);
        t[i]=min(t[2*i],t[2*i+1]);
    }
    void reset(int i,int l,int r){
        lz2[i]=1e9;push(i,l,r);
    }
    int qr(int i,int l,int r,int tl,int tr){
        push(i,l,r);
        if(r<tl||l>tr)return 1e9;
        if(r<=tr&&l>=tl)return t[i];
        int m=(l+r)>>1;
        return min(qr(2*i,l,m,tl,tr),qr(2*i+1,m+1,r,tl,tr));
    }
}st2;
struct seg{
    vector<int>v,mx,mn;
    void build(){
        sort(all(v));v.erase(unique(all(v)),v.end());
        mx.resize(2*v.size());
        mn.resize(2*v.size());
        for(int i=0;i<mx.size();i++)mx[i]=-1e9,mn[i]=1e9;
    }
    void update(int i,int sz,int amt){
        i+=sz;mx[i]=max(mx[i],amt),mn[i]=min(mn[i],amt);
        for(i>>=1;i;i>>=1)mx[i]=max(mx[2*i],mx[2*i+1]),mn[i]=min(mn[2*i],mn[2*i+1]);
    }
    int get_max(int l,int r,int sz,int rs=-1e9){
        for(l+=sz,r+=sz;l<r;l>>=1,r>>=1){
            if(l&1)rs=max(rs,mx[l++]);
            if(r&1)rs=max(rs,mx[--r]);
        }return rs;
    }
    int get_min(int l,int r,int sz,int rs=1e9){
        for(l+=sz,r+=sz;l<r;l>>=1,r>>=1){
            if(l&1)rs=min(rs,mn[l++]);
            if(r&1)rs=min(rs,mn[--r]);
        }return rs;
    }
}tl[mxn];
int sequence(int N, std::vector<int> A){
    int n=N;
    for(int i=1;i<=n;i++)g[A[i-1]].pb(i),sg[0].update(1,0,n,i,n,1),sg[1].update(1,0,n,i,n,-1);
    st2.reset(1,0,2*n);int rs=1;
    for(int x=1;x<=n;x++){
        if(g[x].empty())continue;
        for(auto it : g[x])sg[0].update(1,0,n,it,n,-1),sg[1].update(1,0,n,it,n,1);
        vector<t3>v;
        int pv=0,cnt=0;
        for(auto it : g[x]){
            int mx=sg[0].qr(1,0,n,pv,it-1);
            int mn=-sg[1].qr(1,0,n,pv,it-1);
            int id=st2.qr(1,0,2*n,mn+n,mx+n);
            v.pb({mx+cnt,cnt-mx,cnt});
            v.pb({mn+cnt,cnt-mn,cnt});
            tl[x].v.pb(cnt-mx);tl[x].v.pb(cnt-mn);
            if(id!=1e9)rs=max(rs,cnt-id);
            st2.update(1,0,2*n,mn+n,mx+n,cnt++);pv=it;
        }
        int mx=sg[0].qr(1,0,n,pv,n);
        int mn=-sg[1].qr(1,0,n,pv,n);
        v.pb({mx+cnt,cnt-mx,cnt});
        v.pb({mn+cnt,cnt-mn,cnt});
        tl[x].v.pb(cnt-mx);tl[x].v.pb(cnt-mn);
        int id=st2.qr(1,0,2*n,mn+n,mx+n);
        if(id!=1e9)rs=max(rs,cnt-id);
        sort(all(v));
        tl[x].build();
        for(auto [_,it,y] : v){
            int mn=tl[x].get_min(0,ub(tl[x].v,it),tl[x].v.size());
            int mx=tl[x].get_max(0,ub(tl[x].v,it),tl[x].v.size());
            if(mx!=-1e9)rs=max(rs,abs(y-mx));
            if(mn!=1e9)rs=max(rs,abs(y-mn));
            tl[x].update(lb(tl[x].v,it),tl[x].v.size(),y);
        }
        st2.reset(1,0,2*n);
        for(auto it : g[x])sg[0].update(1,0,n,it,n,-1),sg[1].update(1,0,n,it,n,1);
    }return rs;
}
/*int main(){
    cout<<sequence(7, {1, 2, 3, 1, 2, 1, 3});
}*/

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