제출 #1184115

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1184115		Aviansh	Sequence (APIO23_sequence)	C++20	41 / 100	2098 ms	52256 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);
    }
};

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;
    for(int i = 0;i<n;i++){
        for(int s : pos[i]){
            st.update(s,0);
        }
        for(int s = 0;s<pos[i].size();s++){
            for(int e = s+1;e<pos[i].size();e++){
                int lef = pos[i][s];
                int rig = pos[i][e];
                int sum = st.query(lef,rig)[4];
                array<int,5> right = st.query(rig,n-1);
                array<int,5> left = st.query(0,lef);
                int premin = right[0];
                int premax = right[1];
                int sufmin = left[2];
                int sufmax = left[3];
                int lo = premin+sufmin+sum;
                int hi = premax+sufmax+sum;
                int coun = e-s+1;
                //cout << lef << " " << rig << " " << sum << " " << premin << " " << premax << " " << sufmin << " " << sufmax << "\n";
                if(lo>coun||hi<-coun){
                    continue;
                }
                ans=max(ans,coun);
            }
        }
        for(int s : pos[i]){
            st.update(s,-1);
        }
    }
    return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 17 / 17
• Subtask 3: 0 / 7
• Subtask 4: 0 / 12
• Subtask 5: 13 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18