Submission #1184355

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184355		Aviansh	Sequence (APIO23_sequence)	C++20	100 / 100	693 ms	62036 KiB

sequence

#include "sequence.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

using namespace std;

typedef tree<array<int,2>,null_type,less<array<int,2>>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

struct segTree{
    //{prefmin,prefmax,sufmin,sufmax,sum}
    array<int,5> *st;
    array<int,5>def;
    int n;
    segTree(int siz){
        int x = ceil(log2(siz));
        x++;
        st=new array<int,5>[(1<<x)];
        n=siz-1;
        def={0,0,0,0,0};
        fill(st,st+(1<<x),def);
    }
    array<int,5> unite(array<int,5> lef, array<int,5> rig){
        array<int,5>ans;
        ans[0]=min(lef[0],lef[4]+rig[0]);
        ans[1]=max(lef[1],lef[4]+rig[1]);
        ans[2]=min(rig[2],rig[4]+lef[2]);
        ans[3]=max(rig[3],rig[4]+lef[3]);
        ans[4]=lef[4]+rig[4];
        return ans;
    }
    void rupdate(int l, int r, int ind, int i, int val){
        if(i<l||i>r){
            return;
        }
        if(l==r){
            st[ind]={val,val,val,val,val};
            return;
        }
        int mid = (l+r)/2;
        rupdate(l,mid,ind*2+1,i,val);
        rupdate(mid+1,r,ind*2+2,i,val);
        st[ind] = unite(st[ind*2+1],st[ind*2+2]);
    }
    void update(int i, int val){
        rupdate(0,n,0,i,val);
    }
    array<int,5>rquery(int l, int r, int s, int e, int ind){
        if(e<l||s>r){
            return def;
        }
        if(s<=l&&r<=e){
            return st[ind];
        }
        int mid = (l+r)/2;
        return unite(rquery(l,mid,s,e,ind*2+1),rquery(mid+1,r,s,e,ind*2+2));
    }
    array<int,5>query(int l, int r){
        return rquery(0,n,l,r,0);
    }
};

bool check(int x, array<int,5>nums[], int n, vector<int>(&pos)[]){
    for(int o = 0;o<n;o++){
        for(int i = 0;i<=((int)pos[o].size())-x;i++){
            int j = i+x-1;
            int oi = i;
            int oj = j;
            i=pos[o][i];
            j=pos[o][j];
            int sum = nums[j][4]-nums[i][4];
            int mn = nums[j][2]+nums[i][0];
            int mx = nums[j][3]+nums[i][1];
            int lo = mn+sum;
            int hi = mx+sum;
            i=oi;
            j=oj;
            if(lo>x||hi<-x){
                continue;
            }
            return 1;
        }
    }
    return 0;
}

int sequence(int n, vector<int> arr) {
    vector<int>pos[n];
    for(int i = 0;i<n;i++){
        arr[i]--;
        pos[arr[i]].push_back(i);
    }
    segTree st(n);
    for(int i = 0;i<n;i++){
        st.update(i,1);
    }
    int ans = 1;
    array<int,5>nums[n];
    //lefmin,lefmax,rigmin,rigmax,sum
    for(int i = 0;i<n;i++){
        for(int ind : pos[i]){
            array<int,5>pre = st.query(0,ind);
            array<int,5>suf = st.query(ind,n-1);
            nums[ind][1]=pre[3]-1;
            nums[ind][3]=suf[1]-1;
        }
        for(int s : pos[i]){
            st.update(s,-1);
        }
        int cn = 0;
        for(int ind : pos[i]){
            cn++;
            array<int,5>pre = st.query(0,ind);
            array<int,5>suf = st.query(ind,n-1);
            nums[ind][0]=pre[2]+1;
            nums[ind][2]=suf[0]+1;
            nums[ind][4]=pre[4]+cn;
        }
    }
    int lo = 1;
    int hi = n;
    while(lo<hi){
        int mid = (lo+hi+1)/2;
        if(check(mid,nums,n,pos)){
            lo=mid;
        }
        else{
            hi=mid-1;
        }
    }
    return lo;
}

• 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