Submission #850893

#	Time	Username	Problem	Language	Result	Execution time	Memory
850893		adhityamv	Sequence (APIO23_sequence)	C++17	82 / 100	2041 ms	110232 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
const int INF=500001;
struct segtree{
    int n;
    int val;
    bool tp;
    vector<int> seg;
    vector<int> lazy;
    void Build(int l,int r,int pos){
        if(l==r){
            seg[pos]=l*val;
            lazy[pos]=0;
            return;
        }
        int mid=(l+r)/2;
        Build(l,mid,2*pos);
        Build(mid+1,r,2*pos+1);
        if(tp) seg[pos]=min(seg[2*pos],seg[2*pos+1]);
        else seg[pos]=max(seg[2*pos],seg[2*pos+1]);
    }
    void UpdateLazy(int l,int r,int pos){
        if(lazy[pos]==0) return;
        seg[pos]+=lazy[pos];
        if(l!=r){
            lazy[2*pos]+=lazy[pos];
            lazy[2*pos+1]+=lazy[pos];
        }
        lazy[pos]=0;
    }
    void Update(int l,int r,int pos,int ql,int qr){
        UpdateLazy(l,r,pos);
        if(ql<=l && qr>=r){
            lazy[pos]-=2*val;
            UpdateLazy(l,r,pos);
            return;
        }
        if(ql>r || qr<l) return;
        int mid=(l+r)/2;
        Update(l,mid,2*pos,ql,qr);
        Update(mid+1,r,2*pos+1,ql,qr);
        if(tp) seg[pos]=min(seg[2*pos],seg[2*pos+1]);
        else seg[pos]=max(seg[2*pos],seg[2*pos+1]);
    }
    int 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){
            if(tp) return INF;
            else return -INF;
        }
        int mid=(l+r)/2;
        if(tp) return min(Query(l,mid,2*pos,ql,qr),Query(mid+1,r,2*pos+1,ql,qr));
        else return max(Query(l,mid,2*pos,ql,qr),Query(mid+1,r,2*pos+1,ql,qr));
    }
    segtree(int n,int val,bool tp){
        this->n=n;
        this->val=val;
        this->tp=tp;
        for(int i=0;i<4*n;i++){
            seg.push_back(0);
            lazy.push_back(0);
        }
        Build(0,n,1);
    }
};
int sequence(int n,vector<int> A){
    int x=-1;
    int a[n];
    int b[n];
    int cnt[n+1]={};
    vector<int> ind[n+1];
    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 mina=segtree(n,-1,true);
    auto minb=segtree(n,1,true);
    auto maxa=segtree(n,-1,false);
    auto maxb=segtree(n,1,false);
    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;
            mina.Update(0,n,1,i+1,n);
            maxa.Update(0,n,1,i+1,n);
        }
        if(x!=0) for(int i:ind[x-1]){
            b[i]=-1;
            minb.Update(0,n,1,i+1,n);
            maxb.Update(0,n,1,i+1,n);
        }
        int l=0;
        int r=n;
        int m=(l+r+1)/2;
        vector<int> mn1a;
        vector<int> mx1a;
        vector<int> mn2a;
        vector<int> mx2a;
        vector<int> mn1b;
        vector<int> mx1b;
        vector<int> mn2b;
        vector<int> mx2b;
        for(int i=0;i<cnt[x];i++){
            mn1a.push_back(mina.Query(0,n,1,0,ind[x][i]));
            mx1a.push_back(maxa.Query(0,n,1,0,ind[x][i]));
            mn2a.push_back(mina.Query(0,n,1,ind[x][i]+1,n));
            mx2a.push_back(maxa.Query(0,n,1,ind[x][i]+1,n));
            mn1b.push_back(minb.Query(0,n,1,0,ind[x][i]));
            mx1b.push_back(maxb.Query(0,n,1,0,ind[x][i]));
            mn2b.push_back(minb.Query(0,n,1,ind[x][i]+1,n));
            mx2b.push_back(maxb.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(mx1a[i]>=mn2a[i+m-1] && mx2a[i+m-1]>=mn1a[i]){
                    pssble=true;
                    break;
                }
                if(mx1b[i]>=mn2b[i+m-1] && mx2b[i+m-1]>=mn1b[i]){
                    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:71:9: warning: variable 'a' set but not used [-Wunused-but-set-variable]
   71 |     int a[n];
      |         ^
sequence.cpp:72:9: warning: variable 'b' set but not used [-Wunused-but-set-variable]
   72 |     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: 0 / 18