Submission #1288481

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288481		zhangspicyuwu	Sequence (APIO23_sequence)	C++17	100 / 100	687 ms	71256 KiB

sequence

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
//#define int long long
using namespace std;
const int N=5e5+5,M=5e4+5,inf=1e9,mod=1e9+7;
struct S{
    pii seg[4*N];
    int lazy[4*N];
    void build(const int crr,const int l,const int r){
        lazy[crr]=0;
        if(l==r){
            seg[crr]={-l,-l};
            return;
        }
        const int mid=l+r>>1;
        build(crr*2,l,mid);
        build(crr*2+1,mid+1,r);
        seg[crr]={min(seg[crr*2].fi,seg[crr*2+1].fi),max(seg[crr*2].se,seg[crr*2+1].se)};
    }
    void down(const int crr){
        if(lazy[crr]){
            const int x=lazy[crr]; lazy[crr]=0;
            seg[crr*2].fi+=x; seg[crr*2+1].fi+=x;
            seg[crr*2].se+=x; seg[crr*2+1].se+=x;
            lazy[crr*2]+=x; lazy[crr*2+1]+=x;
        }
    }
    void upd(const int crr,const int l,const int r,const int lm,const int rm){
        if(l>rm || lm>r) return;
        if(lm<=l && r<=rm){
            seg[crr].fi+=2; seg[crr].se+=2;
            lazy[crr]+=2;
            return;
        }
        const int mid=l+r>>1;
        down(crr);
        upd(crr*2,l,mid,lm,rm);
        upd(crr*2+1,mid+1,r,lm,rm);
        seg[crr]={min(seg[crr*2].fi,seg[crr*2+1].fi),max(seg[crr*2].se,seg[crr*2+1].se)};
    }
    pii get(const int crr,const int l,const int r,const int lm,const int rm){
        if(l>rm || lm>r) return {1e9,-1e9};
        if(lm<=l && r<=rm) return seg[crr];
        int mid=l+r>>1;
        down(crr);
        pii t1=get(crr*2,l,mid,lm,rm),g2=get(crr*2+1,mid+1,r,lm,rm);
        return {min(t1.fi,g2.fi),max(t1.se,g2.se)};
    }
} seg1,seg2;
bool check(const int l,const int r,const int n){
    int mn=seg2.get(1,0,n,r,n).fi-seg2.get(1,0,n,0,l-1).se;
    int mx=seg1.get(1,0,n,r,n).se-seg1.get(1,0,n,0,l-1).fi;
    if(mn<=0 && mx>=0) return 1;
    else return 0;
}
int sequence(int n, std::vector<int> a){
    seg1.build(1,0,n);
    seg2.build(1,0,n);
    vector<int> pos[n+1];
    int ans=1;
    for(int i=0;i<n;i++){
        pos[a[i]].push_back(i+1);
    }
    //<=x=1
    //>x=-1
    for(int i=1;i<=n;i++){
        if(pos[i].empty()) continue;
        for(auto j:pos[i]) seg1.upd(1,0,n,j,n);
        int l=0;
        for(int j=1;j<pos[i].size();j++){
            while(!check(pos[i][l],pos[i][j],n)) l++;
            ans=max(ans,j-l+1);
        }
        for(auto j:pos[i]) seg2.upd(1,0,n,j,n);
    }
    return ans;
}
//signed main(){
//    //freopen("mushroom.inp","r",stdin);
//    //freopen("mushroom.out","w",stdout);
//    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
////    cout<<sequence(7, {1, 2, 3, 1, 2, 1, 3})<<"\n";
////    cout<<sequence(9, {1, 1, 2, 3, 4, 3, 2, 1, 1})<<"\n";
////    cout<<sequence(14, {2, 6, 2, 5, 3, 4, 2, 1, 4, 3, 5, 6, 3, 2})<<"\n";
//}

• 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