Submission #850987

#	Time	Username	Problem	Language	Result	Execution time	Memory
850987		adhityamv	Sequence (APIO23_sequence)	C++17	100 / 100	1030 ms	106120 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
const int INF=500001;
#define pi pair<int,int>
#define fi first
#define se second
#define mp make_pair
pair<pi,pi> minp(pair<pi,pi> p1,pair<pi,pi> p2){
    return mp(mp(min(p1.fi.fi,p2.fi.fi),min(p1.fi.se,p2.fi.se)),mp(min(p1.se.fi,p2.se.fi),min(p1.se.se,p2.se.se)));
}
struct segtree{
    int n;
    int val;
    bool tp;
    vector<pair<pi,pi>> seg;
    vector<pi> lazy;
    void Build(int l,int r,int pos){
        if(l==r){
            seg[pos]=mp(mp(-l,l),mp(l,-l));
            lazy[pos]=mp(0,0);
            return;
        }
        int mid=(l+r)/2;
        Build(l,mid,2*pos);
        Build(mid+1,r,2*pos+1);
        seg[pos]=minp(seg[2*pos],seg[2*pos+1]);
    }
    void UpdateLazy(int l,int r,int pos){
        if(lazy[pos]==mp(0,0)) return;
        seg[pos]=mp(mp(seg[pos].fi.fi+lazy[pos].fi,seg[pos].fi.se-lazy[pos].fi),mp(seg[pos].se.fi+lazy[pos].se,seg[pos].se.se-lazy[pos].se));
        if(l!=r){
            lazy[2*pos]=mp(lazy[2*pos].fi+lazy[pos].fi,lazy[2*pos].se+lazy[pos].se);
            lazy[2*pos+1]=mp(lazy[2*pos+1].fi+lazy[pos].fi,lazy[2*pos+1].se+lazy[pos].se);
        }
        lazy[pos]=mp(0,0);
    }
    void Update(int l,int r,int pos,int ql,int qr,int tp){
        UpdateLazy(l,r,pos);
        if(ql<=l && qr>=r){
            if(tp==0)lazy[pos]=mp(lazy[pos].fi+2,lazy[pos].se);
            else lazy[pos]=mp(lazy[pos].fi,lazy[pos].se-2);
            UpdateLazy(l,r,pos);
            return;
        }
        if(ql>r || qr<l) return;
        int mid=(l+r)/2;
        Update(l,mid,2*pos,ql,qr,tp);
        Update(mid+1,r,2*pos+1,ql,qr,tp);
        seg[pos]=minp(seg[2*pos],seg[2*pos+1]);
    }
    pair<pi,pi> Query(int l,int r,int pos,int ql,int qr){
        UpdateLazy(l,r,pos);
        if(ql<=l && qr>=r){
            return seg[pos];
        }
        if(ql>r || qr<l){
            return mp(mp(INF,INF),mp(INF,INF));
        }
        int mid=(l+r)/2;
        return minp(Query(l,mid,2*pos,ql,qr),Query(mid+1,r,2*pos+1,ql,qr));
    }
    segtree(int n){
        this->n=n;
        for(int i=0;i<4*n+4;i++){
            seg.push_back(mp(mp(0,0),mp(0,0)));
            lazy.push_back(mp(0,0));
        }
        Build(0,n,1);
    }
};
int sequence(int n,vector<int> A){
    int x=-1;
    int a[n];
    int b[n];
    int cnt[n]={};
    vector<int> ind[n];
    for(int i=0;i<n;i++){
        A[i]--;
        cnt[A[i]]++;
        ind[A[i]].push_back(i);
    }
    for(int i=0;i<n;i++){
        a[i]=-1;
        b[i]=1;
    }
    auto st=segtree(n);
    int ans=0;
    sort(A.begin(),A.end());
    ans=max(ans,cnt[A[(n)/2]]);
    ans=max(ans,cnt[A[(n+1)/2]]);
    while(x<n-1){
        x++;
        for(int i:ind[x]){
            a[i]=1;
            st.Update(0,n,1,i+1,n,0);
        }
        if(x!=0) for(int i:ind[x-1]){
            b[i]=-1;
            st.Update(0,n,1,i+1,n,1);
        }
        int l=0;
        int r=n;
        int m=(l+r+1)/2;
        vector<pair<pi,pi>> t1;
        vector<pair<pi,pi>> t2;
        for(int i=0;i<cnt[x];i++){
            t1.push_back(st.Query(0,n,1,0,ind[x][i]));
            t2.push_back(st.Query(0,n,1,ind[x][i]+1,n));
        }
        while(l!=r){
            bool pssble=false;
            for(int i=0;i<cnt[x]-m+1;i++){
                if(-t1[i].fi.se>=t2[i+m-1].fi.fi && -t2[i+m-1].fi.se>=t1[i].fi.fi){
                    pssble=true;
                    break;
                }
                if(-t1[i].se.se>=t2[i+m-1].se.fi && -t2[i+m-1].se.se>=t1[i].se.fi){
                    pssble=true;
                    break;
                }
            }
            if(pssble) l=m;
            else r=m-1;
            m=(l+r+1)/2;
        }
        ans=max(ans,m);
    }
    return ans;
}

Compilation message (stderr)

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:73:9: warning: variable 'a' set but not used [-Wunused-but-set-variable]
   73 |     int a[n];
      |         ^
sequence.cpp:74:9: warning: variable 'b' set but not used [-Wunused-but-set-variable]
   74 |     int b[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