Submission #1198675

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198675		KhoaDuy	Sequence (APIO23_sequence)	C++17	100 / 100	721 ms	79504 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
struct T{
    int Minpre=0,Maxpre=0,Minsuf=0,Maxsuf=0,sum=0;
};
T TT(T &le,T &ri){
    T pa;
    pa.sum=le.sum+ri.sum;
    pa.Minpre=min(le.Minpre,le.sum+ri.Minpre);
    pa.Maxpre=max(le.Maxpre,le.sum+ri.Maxpre);
    pa.Minsuf=min(ri.Minsuf,le.Minsuf+ri.sum);
    pa.Maxsuf=max(ri.Maxsuf,le.Maxsuf+ri.sum);
    return pa;
}
T Tid;
struct segtree{
    vector<T> seg;
    int n,lg;
    void refresh(int v){
        seg[v]=TT(seg[v<<1],seg[(v<<1)|1]);
    }
    void build(int siz){
        n=1;
        while(n<siz){
            n<<=1;
        }
        lg=__lg(n);
        seg.assign(n<<1,Tid);
    }
    void update(int l,int x){
        l+=n;
        seg[l].sum=x;
        seg[l].Minpre=min(0,x),seg[l].Maxpre=max(0,x);
        seg[l].Minsuf=seg[l].Minpre,seg[l].Maxsuf=seg[l].Maxpre;
        for(int i=1;i<=lg;i++){
            refresh(l>>i);
        }
    }
    T query(int l,int r){
        l+=n,r+=n;
        T le=Tid,ri=Tid;
        for(;l<r;l>>=1,r>>=1){
            if(l&1){
                le=TT(le,seg[l]);
                l++;
            }
            if(r&1){
                r--;
                ri=TT(seg[r],ri);
            }
        }
        return TT(le,ri);
    }
};
struct fenwick{
    vector<int> bit;
    void build(int siz){
        bit.resize(siz+1);
        for(int i=1;i<=siz;i++){
            bit[i]=1e9;
        }
    }
    void update(int i,int x){
        for(;i<bit.size();i+=(i&(-i))){
            bit[i]=min(bit[i],x);
        }
    }
    int query(int i){
        int curr=1e9;
        for(;i;i-=(i&(-i))){
            curr=min(curr,bit[i]);
        }
        return curr;
    }
};
struct point{
    int x,y,idx,ope;
};
bool cmp(point &a,point &b){
    if(a.x!=b.x){
        return (a.x<b.x);
    }
    return (a.ope<b.ope);
}
int sequence(int n,vector<int> a){
    segtree seg;
    vector<vector<int>> occu(n+1);
    for(int i=0;i<n;i++){
        occu[a[i]].push_back(i);
    }
    seg.build(n);
    for(int i=0;i<n;i++){
        seg.update(i,1);
    }
    int ans=1;
    for(int x=1;x<=n;x++){
        int sz=occu[x].size();
        for(int i=0;i<sz;i++){
            seg.update(occu[x][i],0);
        }
        if(sz==0){
            continue;
        }
        vector<point> v;
        int sum=0;
        map<int,int> mp;
        for(int i=0;i<sz;i++){
            int pos=occu[x][i],last=-1,nxt=n;
            if(i>0){
                last=occu[x][i-1];
            }
            if(i+1<sz){
                nxt=occu[x][i+1];
            }
            T suf=seg.query(last+1,pos+1);
            T pre=seg.query(pos,nxt);
            sum+=suf.sum;
            mp[i-1+sum-suf.Maxsuf]=1;
            mp[sum+pre.Maxpre+i]=1;
            v.push_back({suf.Minsuf+i-1-sum,i-1+sum-suf.Maxsuf,i,0});
            v.push_back({i-sum-pre.Minpre,sum+pre.Maxpre+i,i,1});
        }
        int idx=1;
        for(pair<const int,int> &x:mp){
            x.second=idx,idx++;
        }
        sort(v.begin(),v.end(),cmp);
        fenwick bit;
        bit.build(idx-1);
        for(point &x:v){
            x.y=mp[x.y];
            if(x.ope==0){
                bit.update(x.y,x.idx);
            }
            else{
                ans=max(ans,x.idx-bit.query(x.y)+1);
            }
        }
        for(int i=0;i<sz;i++){
            seg.update(occu[x][i],-1);
        }
    }
    return ans;
}
/*signed 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: 13 / 13
• Subtask 6: 22 / 22
• Subtask 7: 18 / 18