Submission #750038

#	Time	Username	Problem	Language	Result	Execution time	Memory
750038		bachhoangxuan	Sequence (APIO23_sequence)	C++17	100 / 100	957 ms	74704 KiB

sequence

#include "sequence.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define piii pair<int,pii>
#define fi first
#define se second
struct rn{//range
    int l=0,r=0;
    friend rn operator+(rn a,rn b){
        return {a.l+b.l,a.r+b.r};
    }
};
struct node{
    int sum=0;
    rn p,s;
    node(int x=0){
        p.r=max(p.r,x);p.l=min(p.l,x);
        s.r=max(s.r,x);s.l=min(s.l,x);
        sum+=x;
    }
    friend node operator+(node a,node b){
        node res;res.sum=a.sum+b.sum;
        res.p.r=max(a.p.r,a.sum+b.p.r);
        res.p.l=min(a.p.l,a.sum+b.p.l);
        res.s.r=max(b.s.r,b.sum+a.s.r);
        res.s.l=min(b.s.l,b.sum+a.s.l);
        return res;
    }
};
vector<int> a,com;
namespace Segtree{
    vector<node> tree;
    void build(int l,int r,int id){
        if(id==1) tree.resize(4*r);
        if(l==r){tree[id]=node(1);return;}
        int mid=(l+r)>>1;
        build(l,mid,id<<1);build(mid+1,r,id<<1|1);
        tree[id]=tree[id<<1]+tree[id<<1|1];
    }
    void update(int l,int r,int id,int p){
        if(l==r){tree[id]=node(-1);return;}
        int mid=(l+r)>>1;
        if(p<=mid) update(l,mid,id<<1,p);
        else update(mid+1,r,id<<1|1,p);
        tree[id]=tree[id<<1]+tree[id<<1|1];
    }
    node query(int l,int r,int id,int tl,int tr){
        if(r<tl || tr<l || tl>tr) return node(0);
        if(tl<=l && r<=tr) return tree[id];
        int mid=(l+r)>>1;
        return query(l,mid,id<<1,tl,tr)+query(mid+1,r,id<<1|1,tl,tr);
    }
};
int sequence(int n,vector<int> A){
    a.resize(n+1);
    for(int i=1;i<=n;i++){a[i]=A[i-1];com.push_back(a[i]);}
    sort(com.begin(),com.end());
    com.erase(unique(com.begin(),com.end()),com.end());
    vector<vector<int>> pos(n+1,vector<int>());
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(com.begin(),com.end(),a[i])-com.begin()+1;
        pos[a[i]].push_back(i);
    }
    int ans=0;
    {//cal cnt(l,r) with (r-l+1)%2==0
        Segtree::build(1,n,1);
        for(int i=1;i<=(int)com.size();i++){
            int sz=(int)pos[i].size(),sum=Segtree::tree[1].sum;
            vector<rn> lt(sz),rt(sz);
            for(int j=sz-1;j>=0;j--) rt[j]=Segtree::query(1,n,1,pos[i][j]+1,n).s;
            for(int j=0;j<sz;j++){
                lt[j]=Segtree::query(1,n,1,1,pos[i][j]-1).p;
                Segtree::update(1,n,1,pos[i][j]);
            }
            auto check = [&](int mid){
                for(int j=0;j<=sz-mid;j++){
                    rn x=lt[j]+rt[j+mid-1];
                    if(max(x.l,sum-2*j-2*mid)<=min(x.r,sum-2*j)) return true;
                }
                return false;
            };
            int l=1,r=sz,res=1;
            while(r>=l){
                int mid=(l+r)>>1;
                if(check(mid)) res=mid,l=mid+1;
                else r=mid-1;
            }
            ans=max(ans,res);
        }
    }
    {//cal cnt(1,n)
        int res=0;sort(a.begin(),a.end());
        for(int i=1;i<=n;i++) res+=(a[i]==a[(n+1)/2]);
        ans=max(ans,res);
    }
    return ans;
}

• 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