Submission #1202878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202878		irmuun	Sequence (APIO23_sequence)	C++17	40 / 100	596 ms	80644 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const int N=5e5+5;

int n,a[N],lo,hi;
vector<int>pos[N];

struct segtree{
    int mx[4*N],mn[4*N],lazy[4*N];
    void add(int v,int x){
        mx[v]+=x;
        mn[v]+=x;
        lazy[v]+=x;
    }
    void push(int v){
        if(lazy[v]==0) return;
        add(v<<1,lazy[v]);
        add(v<<1|1,lazy[v]);
        lazy[v]=0;
    }
    void merge(int v){
        mx[v]=max(mx[v<<1],mx[v<<1|1]);
        mn[v]=min(mn[v<<1],mn[v<<1|1]);
    }
    void update(int v,int l,int r,int L,int R,int val){
        if(R<L||r<L||R<l) return;
        if(L<=l&&r<=R){
            add(v,val);
            return;
        }
        push(v);
        int m=(l+r)>>1;
        update(v<<1,l,m,L,R,val);
        update(v<<1|1,m+1,r,L,R,val);
        merge(v);
    }
    void query(int v,int l,int r,int L,int R){
        if(R<L||r<L||R<l) return;
        if(L<=l&&r<=R){
            lo=min(lo,mn[v]);
            hi=max(hi,mx[v]);
            return;
        }
        push(v);
        int m=(l+r)>>1;
        query(v<<1,l,m,L,R);
        query(v<<1|1,m+1,r,L,R);
    }
};

int sequence(int N,vector<int>A){
    n=N;
    for(int i=1;i<=n;i++){
        a[i]=A[i-1];
        pos[a[i]].pb(i);
    }
    segtree more,less;
    for(int i=1;i<=n;i++){
        more.update(1,1,n,i,n,-1);
    }
    for(int i=1;i<=n;i++){
        less.update(1,1,n,i,n,-1);
    }
    int ans=0;
    for(int x=1;x<=n;x++){
        for(int p:pos[x]){
            more.update(1,1,n,p,n,+2);
        }
        int j=0;
        for(int i=0;i<pos[x].size();i++){
            while(j<i){
                int v1,v2;
                hi=-1e9,more.query(1,1,n,pos[x][i],n);
                v1=hi;
                lo=0,more.query(1,1,n,1,pos[x][j]-1);
                v1-=lo;
                lo=1e9,less.query(1,1,n,pos[x][i],n);
                v2=lo;
                hi=0,less.query(1,1,n,1,pos[x][j]-1);
                v2-=hi;
                if(v1*v2>0) j++;
                else break;
            }
            ans=max(ans,i-j+1);
        }
        for(int p:pos[x]){
            less.update(1,1,n,p,n,+2);
        }
    }
    return ans;
}

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