Submission #908374

#	Time	Username	Problem	Language	Result	Execution time	Memory
908374		winter0101	Sequence (APIO23_sequence)	C++17	100 / 100	1827 ms	82252 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
const int maxn=5e5+9;
int ss[maxn];
struct IT_lazy{
int mx[maxn<<2],mn[maxn<<2],lazy[maxn<<2];
void build(int id,int l,int r){
lazy[id]=0;
if (l==r){
mx[id]=mn[id]=ss[l];
return;
}
int mid=(l+r)>>1;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
mx[id]=max(mx[id<<1],mx[id<<1|1]);
mn[id]=min(mn[id<<1],mn[id<<1|1]);
}
void resz(int n){
build(1,1,n);
}
void push(int id){
if (lazy[id]){
    mx[id<<1]+=lazy[id];
    mx[id<<1|1]+=lazy[id];
    mn[id<<1]+=lazy[id];
    mn[id<<1|1]+=lazy[id];
    lazy[id<<1]+=lazy[id];
    lazy[id<<1|1]+=lazy[id];
    lazy[id]=0;
}
}
void update(int id,int l,int r,int u,int v,int val){
if (l>v||r<u||u>v)return;
if (u<=l&&r<=v){
    mx[id]+=val;
    mn[id]+=val;
    lazy[id]+=val;
    return;
}
push(id);
int mid=(l+r)>>1;
update(id<<1,l,mid,u,v,val);
update(id<<1|1,mid+1,r,u,v,val);
mx[id]=max(mx[id<<1],mx[id<<1|1]);
mn[id]=min(mn[id<<1],mn[id<<1|1]);
}
int get_max(int id,int l,int r,int u,int v){
if (l>v||r<u||u>v)return -maxn;
if (u<=l&&r<=v)return mx[id];
int mid=(l+r)>>1;
push(id);
return max(get_max(id<<1,l,mid,u,v),get_max(id<<1|1,mid+1,r,u,v));
}
int get_min(int id,int l,int r,int u,int v){
if (l>v||r<u||u>v)return maxn;
if (u<=l&&r<=v)return mn[id];
int mid=(l+r)>>1;
push(id);
return min(get_min(id<<1,l,mid,u,v),get_min(id<<1|1,mid+1,r,u,v));
}
};
struct IT{
int st[maxn*4];
void update(int id,int l,int r,int u,int val){
if(l>u||r<u)return;
if (l==r){
    st[id]=val;
    return;
}
int mid=(l+r)>>1;
if (mid>=u)update(id<<1,l,mid,u,val);
else update(id<<1|1,mid+1,r,u,val);
st[id]=max(st[id<<1],st[id<<1|1]);
}
int walk(int id,int l,int r,int val){
if (st[id]<val)return -1;
if (l==r)return l;
int mid=(l+r)>>1;
int ans=walk(id<<1,l,mid,val);
if (ans==-1)return walk(id<<1|1,mid+1,r,val);
return ans;
}
};
int n;
int a[maxn];
vector<int>value[maxn];
int mx_l[maxn],mn_l[maxn],mn_r[maxn],mx_r[maxn];
int pf[maxn];
void pre(){
    IT_lazy st;
    for1(i,1,n)ss[i]=-i;
    st.resz(n);
    auto up=[&](int id,int val){
    st.update(1,1,n,id,n,val);
    };
    for1(i,1,n){
    for (auto v:value[i]){
    up(v,2);
    }
    for (auto v:value[i]){
    pf[v]=st.get_max(1,1,n,v,v);
    }
    for1(j,0,sz(value[i])-1){
    int v=value[i][j];
    if (j==sz(value[i])-1)mx_r[v]=st.get_max(1,1,n,v,n)-pf[v],mn_r[v]=st.get_min(1,1,n,v,n)-pf[v];
    else mx_r[v]=st.get_max(1,1,n,v,value[i][j+1]-1)-pf[v],mn_r[v]=st.get_min(1,1,n,v,value[i][j+1]-1)-pf[v];
    }
    }
    ss[n+1]=0;
    for2(i,n,1)ss[i]=ss[i+1]-1;
    st.resz(n);
    auto rup=[&](int id,int val){
    st.update(1,1,n,1,id,val);
    };
    for1(i,1,n){
    for (auto v:value[i])rup(v,2);
    for1(j,0,sz(value[i])-1){
    int v=value[i][j];
    int suffix=st.get_max(1,1,n,v,v);
    if (j==0){
    mx_l[v]=st.get_max(1,1,n,1,v)-suffix,mn_l[v]=st.get_min(1,1,n,1,v)-suffix;
    }
    else {
    mx_l[v]=st.get_max(1,1,n,value[i][j-1]+1,v)-suffix,mn_l[v]=st.get_min(1,1,n,value[i][j-1]+1,v)-suffix;
    }
    }
    }
}
struct type{
int id,val;
bool fl;
bool operator < (const type &p){
if (val==p.val)return fl<p.fl;
return val<p.val;
}
};
int sequence(int N, std::vector<int> A) {
    n=N;
    for1(i,1,n)a[i]=A[i-1];
    for1(i,1,n)value[a[i]].pb(i);
    int ans=0;
    pre();
    IT st;
    for1(i,1,n){
    vector<type>t;
    for1(j,0,sz(value[i])-1){
    int v=value[i][j];
    t.pb({j+1,pf[v]-mx_l[v],0});
    t.pb({j+1,pf[v]+1+mx_r[v],1});
    }
    sort(all(t));
    int m=sz(value[i]);
    for1(j,1,4*m)st.st[j]=-n*10;
    for (auto v:t){
    int id=value[i][v.id-1];
    if (v.fl==0){
    st.update(1,1,m,v.id,pf[id]-mn_l[id]-2*v.id);
    }
    else {
    int pos=st.walk(1,1,m,pf[id]+1+mn_r[id]-2*v.id-2);
    if (pos!=-1&&pos<=v.id){
    ans=max(ans,v.id-pos+1);
    }
    }
    }
    }
    return ans;
}
/*signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    freopen("temp.INP","r",stdin);
    //freopen(".OUT","w",stdout);
    int N;
    assert(1 == scanf("%d", &N));

    std::vector<int> A(N);
    for (int i = 0; i < N; ++i) {
    assert(1 == scanf("%d", &A[i]));
    }
    int result = sequence(N, A);
    printf("%d\n", result);
    return 0;
}*/

• 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