Submission #1288955

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288955		nikolashami	Sequence (APIO23_sequence)	C++20	100 / 100	603 ms	83888 KiB

sequence

#include<bits/stdc++.h>
#include"sequence.h"
using namespace std;
using ll=long long;

#pragma GCC optimize("O3")
const ll N1=5e5+5;
vector<ll>pos[N1];
ll a[N1],n;

struct node{
	ll mx,mn,sum;
}st[4*N1];

node mrg(node x,node y){
	node ret;
	ret.sum=x.sum+y.sum;
	ret.mn=min(x.mn,x.sum+y.mn);
	ret.mx=max(x.mx,x.sum+y.mx);
	return ret;
}

void bd(ll i=1,ll l=1,ll r=n){
	if(l==r){
		if(a[l]==1)st[i].sum=0;
		else st[i].sum=1;
		st[i].mx=st[i].sum;
		st[i].mn=0;
		return;
	}
	ll md=(l+r)/2;
	bd(i*2,l,md);
	bd(i*2+1,md+1,r);
	st[i]=mrg(st[i*2],st[i*2+1]);
}

void upd(ll id,ll x,ll i=1,ll l=1,ll r=n){
	if(l==r){
		st[i].sum=x;
		st[i].mn=min((ll)0,st[i].sum);
		st[i].mx=max((ll)0,st[i].sum);
		return;
	}
	ll md=(l+r)/2;
	if(id<=md)upd(id,x,i*2,l,md);
	else upd(id,x,i*2+1,md+1,r);
	st[i]=mrg(st[i*2],st[i*2+1]);
}

node qry(ll l,ll r,ll i=1,ll tl=1,ll tr=n){
	if(tl>=l&&tr<=r)return st[i];
	ll md=(tl+tr)/2;
	node ret={-(ll)2e9,(ll)2e9,(ll)0};
	if(md>=l)ret=mrg(ret,qry(l,r,i*2,tl,md));
	if(md+1<=r)ret=mrg(ret,qry(l,r,i*2+1,md+1,tr));
	return ret;
}

array<ll,2>getR(ll j,ll x){
	ll p2=pos[x][j];
	node RG=qry(p2,n);
	node M=qry(1,p2-1);
	array<ll,2>rgt={M.sum+RG.mn,M.sum+RG.mx};
	return rgt;
}

array<ll,2>getL(ll i,ll x){
	ll p1=pos[x][i];
	node LF=(p1!=1?qry(1,p1-1):(node){0,0,0});
	array<ll,2>lef={LF.mn,LF.mx};
	return lef;
}

ll L1[N1],R1[N1],L2[N1],R2[N1];

struct{
	ll mn,mx;
}ST[4*N1];

void bd2(ll i,ll l,ll r){
	if(l==r){
		ST[i].mx=R1[l]-l;
		ST[i].mn=L1[l]+l;
		return;
	}
	ll md=(l+r)/2;
	bd2(i*2,l,md);
	bd2(i*2+1,md+1,r);
	ST[i].mx=max(ST[i*2].mx,ST[i*2+1].mx);
	ST[i].mn=min(ST[i*2].mn,ST[i*2+1].mn);
}

ll Q(ll i,ll X,ll Y,ll tl,ll tr,ll l,ll r){
	if(tr<l||tl>r||ST[i].mx<X||ST[i].mn>Y)return 1e18;
	if(tl==tr)return tr;
	ll md=(tl+tr)/2,rt=Q(i*2,X,Y,tl,md,l,r);
	if(rt!=1e18)return rt;
	return Q(i*2+1,X,Y,md+1,tr,l,r);
}

ll sol(ll x){
	ll sz=pos[x].size();
	if(!sz)return 0;

	for(int i=0;i<sz;++i){
		array<ll,2>TMP=getL(i,x);
		L1[i]=TMP[0];
		R1[i]=TMP[1];
		if(!i)continue;
		TMP=getR(i,x);
		L2[i]=TMP[0];
		R2[i]=TMP[1];
	}

	for(int i=0;i<=4*sz;++i){
		ST[i].mn=1e18;
		ST[i].mx=-1e18;
	}

	bd2(1,0,sz-1);

	ll ret=1;
	for(int i=1;i<sz;++i)
		ret=max(ret,1+i-Q(1,L2[i]-i-1,R2[i]+i+1,0,sz-1,0,i-1));

	//sad ocu da uzmem (l<r) t.d. 
	//1) [l1,r1] i [l2,r2] se seku
	//ili l1 element [l2,r2], ili r1 element [l2,r2]
	//2) l2-r1 <= r-l+1, l2-r1>=0 
	//l-r1 <= r-l2+1, r1<=l2, najmanje l t.d.
	//3) l1-r2 <= r-l+1, l1-r2>=0
	//l+l1 <= r+r2+1, l1>=r2

	return ret;
}

int sequence(int _n,vector<int>_a){
	n=_n;
	for(int i=1;i<=n;++i)
		a[i]=_a[i-1];

	for(int i=1;i<=n;++i)
		pos[i].clear();
	for(int i=1;i<=n;++i)
		pos[a[i]].push_back(i);


	bd(); //za 1
	ll ans=sol(1),MM=*max_element(a+1,a+n+1);
	//ll ans=sol(4);

	for(int i=2;i<=MM;++i){
		for(ll x:pos[i-1])upd(x,-1);
		for(ll x:pos[i])upd(x,0);
		ll D=sol(i);
		ans=max(ans,D);
	}

	return ans;
}

//signed main(){cout<<sequence(9, {1, 1, 2, 3, 4, 3, 2, 1, 1});}

• 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