제출 #1273203

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273203		imarn	서열 (APIO23_sequence)	C++20	7 / 100	2099 ms	98680 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{
    int t[16*mxn]{0};
    void build(){
        for(int i=0;i<8*mxn;i++)t[i]=1e9;
    }
    void update(int i,int l,int r,int idx,int v){
        if(r<idx||l>idx)return;
        if(l==r){
            t[i]=min(t[i],v);
            return;
        }int m=(l+r)>>1;
        update(2*i,l,m,idx,v);update(2*i+1,m+1,r,idx,v);
        t[i]=min(t[2*i],t[2*i+1]);
    }
    void reset(int i,int l,int r,int idx,int v){
        if(r<idx||l>idx)return;
        if(l==r){
            t[i]=v;
            return;
        }int m=(l+r)>>1;
        reset(2*i,l,m,idx,v);reset(2*i+1,m+1,r,idx,v);
        t[i]=min(t[2*i],t[2*i+1]);
    }
    int qr(int i,int l,int r,int tl,int tr){
        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));
    }
}tr[2];
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;tr[0].build();tr[1].build();
    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});
            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-mx,cnt});
        int id=st2.qr(1,0,2*n,mn+n,mx+n);
        if(id!=1e9)rs=max(rs,cnt-id);
        sort(all(v));
        for(auto [_,x,y] : v){
            int mn=tr[0].qr(1,0,4*n,0,x+2*n);
            int mx=-tr[1].qr(1,0,4*n,0,x+2*n);
            if(mx!=-1e9)rs=max(rs,abs(y-mx));
            if(mn!=1e9)rs=max(rs,abs(y-mn));
            tr[0].update(1,0,4*n,x+2*n,y);
            tr[1].update(1,0,4*n,x+2*n,-y);
        }
        for(auto [_,x,y] : v){
            tr[0].reset(1,0,4*n,x+2*n,1e9);
            tr[1].reset(1,0,4*n,x+2*n,1e9);
        }
        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: 0 / 11
• Subtask 2: 0 / 17
• Subtask 3: 7 / 7
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18