Submission #1093397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093397		alexander707070	Sequence (APIO23_sequence)	C++17	28 / 100	2045 ms	548340 KiB

sequence

#include<bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#define MAXN 500007
using namespace std;
 
int n,a[MAXN],ans,c[MAXN];
 
vector<int> poss[MAXN];
 
const int bucket_sz=200;
 
struct node{
	int sum;
	int minpref,maxpref;
 
	inline friend node operator + (node fr,node sc){
		return {fr.sum+sc.sum,min(fr.minpref,fr.sum+sc.minpref),max(fr.maxpref,fr.sum+sc.maxpref)};
	}
}curr;
 
struct ST{
	node tree[4*MAXN];
 
	void update(int v,int l,int r,int pos,int val){
		if(l==r){
			tree[v].sum=val;
			tree[v].minpref=min(val,0);
			tree[v].maxpref=max(val,0);
		}else{
			int tt=(l+r)/2;
			if(pos<=tt)update(2*v,l,tt,pos,val);
			else update(2*v+1,tt+1,r,pos,val);
 
			tree[v]=tree[2*v]+tree[2*v+1];
		}
	}
 
	node getinfo(int v,int l,int r,int ll,int rr){
		if(ll>rr)return {0,0,0};
		if(l==ll and r==rr){
			return tree[v];
		}else{
			int tt=(l+r)/2;
			return getinfo(2*v,l,tt,ll,min(tt,rr)) + getinfo(2*v+1,tt+1,r,max(tt+1,ll),rr);
		}
	}
}seg;
 
struct nodd{
	int l,r,val;
};
 
nodd t[200*MAXN];
int num;
 
struct ST2{
 
	int root;
 
	void init(){
		num++;
		t[num]={0,0,10*n};
		root=num;
	}
 
	void addnode(){
		num++;
		if(num>=200*MAXN)cout<<1/0;
 
		t[num]={0,0,10*n};
	}
 
	void check(int v){
		if(t[v].l==0){
			addnode(); t[v].l=num;
		}
 
		if(t[v].r==0){
			addnode(); t[v].r=num;
		}
	}
 
	void update(int v,int l,int r,int pos,int val){
		if(l==r){
			t[v].val=min(val,t[v].val);
		}else{
			int tt=(l+r)/2;
			check(v);
 
			if(pos<=tt)update(t[v].l,l,tt,pos,val);
			else update(t[v].r,tt+1,r,pos,val);
 
			t[v].val=min(t[t[v].l].val,t[t[v].r].val);
		}
	}
 
	int getmin(int v,int l,int r,int ll,int rr){
		if(v==0 or ll>rr)return 10*n;
		if(l==ll and r==rr)return t[v].val;
 
		int tt=(l+r)/2;
		return min( getmin(t[v].l,l,tt,ll,min(tt,rr)) , getmin(t[v].r,tt+1,r,max(tt+1,ll),rr) );
	}
}segx[2*MAXN],segy[2*MAXN];
 
int solve(int val){
 
	int res=0;
	for(int ii=0;ii<poss[val].size();ii++){
		for(int ff=ii;ff<poss[val].size();ff++){
			int i=poss[val][ii];
			int f=poss[val][ff];
 
			int sum=seg.getinfo(1,1,n,i+1,f-1).sum;
			curr=seg.getinfo(1,1,n,f,n);
			int minpref=curr.minpref,maxpref=curr.maxpref;
			
			curr=seg.getinfo(1,1,n,1,i);
			int minsuff=curr.sum-curr.maxpref,maxsuff=curr.sum-curr.minpref;
 
			if((ff-ii+1)>=sum+minpref+minsuff and (ff-ii+1)>=-sum-maxpref-maxsuff)res=max(res,(ff-ii+1));
		}
	}
 
	return res;
}
 
struct event{
	int val,x,y;
 
	inline friend bool operator < (event fr,event sc){
		if(fr.val==sc.val and fr.x==sc.x)return fr.y<sc.y;
		if(fr.val==sc.val)return fr.x<sc.x;
		return fr.val<sc.val;
	}
 
};
 
set<event> xx,yy;
 
int A,B,C;
 
void incrx(){
	xx.insert({segx[B-(A-C)+n].getmin(segx[B-(A-C)+n].root,0,2*n,0,B+(A-C)+n),B-(A-C)+n,B+(A-C)+n});
}
 
void incry(){
	yy.insert({segy[B+(A-C)+n].getmin(segy[B+(A-C)+n].root,0,2*n,0,B-(A-C)+n),B-(A-C)+n,B+(A-C)+n});
}
 
int mins(){
	while(!xx.empty()){
		auto it=xx.begin();
		event curr=*it;
 
		if(curr.x>B-(A-C)+n){
			xx.erase(it); 
			continue;
		}
 
		if(curr.y>B+(A-C)+n){
			xx.erase(it); 
			
			if(curr.x<=B-(A-C)+n){
				xx.insert({segx[curr.x].getmin(segx[curr.x].root,0,2*n,0,B+(A-C)+n),curr.x,B+(A-C)+n});
			}

			continue;
		}
 
		break;
	}
 
	while(!yy.empty()){
		auto it=yy.begin();
		event curr=*it;
 
		if(curr.x>B-(A-C)+n){
			yy.erase(it); 

			if(curr.y<=B+(A-C)+n){
				yy.insert({segy[curr.y].getmin(segy[curr.y].root,0,2*n,0,B-(A-C)+n),B-(A-C)+n,curr.y});
			}
			continue;
		}
 
		if(curr.y>B+(A-C)+n){
			yy.erase(it); continue;
		}
 
		break;
	}
 
	int res=10*n;
 
	if(!xx.empty()){
		auto it=xx.begin();
		event s=*it; res=min(res,s.val);
	}
 
	if(!yy.empty()){
		auto it=yy.begin();
		event s=*it; res=min(res,s.val);
	}
 
	return res;
}
 
int bigsolve(int val){
 
	int res=0;
	A=B=C=0;
 
	xx.clear(); yy.clear();
 
	num=0;
	for(int i=0;i<=2*n;i++){
		segx[i].init(); segy[i].init();
	}
 
	segx[n].update(segx[n].root,0,2*n,n,0);
	segy[n].update(segy[n].root,0,2*n,n,0);
 
	xx.insert({0,n,n});
	yy.insert({0,n,n});
	
	for(int i=1;i<=n;i++){

		if(a[i]>val)A++;
		if(a[i]<val)C++;
		if(a[i]==val)B++;
 
		segx[B-(A-C)+n].update(segx[B-(A-C)+n].root,0,2*n,B+(A-C)+n,B);
		segy[B+(A-C)+n].update(segy[B+(A-C)+n].root,0,2*n,B-(A-C)+n,B);
		
		incrx(); incry();
 
		res=max(res,B-mins());
	}
 
	return res;
}
 
int sequence(int N, std::vector<int> A){
	n=N;

	for(int i=1;i<=n;i++){
		a[i]=A[i-1];
		poss[a[i]].push_back(i);
 
		seg.update(1,1,n,i,1);
	}
 
	for(int i=1;i<=n;i++){
		for(int f:poss[i-1])seg.update(1,1,n,f,-1);
		for(int f:poss[i])seg.update(1,1,n,f,0);

		if(n<=2000){
		if(poss[i].size()<=bucket_sz)ans=max(ans,solve(i));
		else ans=max(ans,bigsolve(i));
		}else{
			if(poss[i].size()>bucket_sz)ans=max(ans,bigsolve(i));
		}
	}

	return ans;
}
 
/*int main(){
	
	while(true){
		sequence(10, {1,1,1,1,1,1,1,1,1,1});
	}

	//cout<<sequence(14, {2, 6, 2, 5, 3, 4, 2, 1, 4, 3, 5, 6, 3, 2})<<"\n";
	
	return 0;
}*/

Compilation message (stderr)

sequence.cpp: In member function 'void ST2::addnode()':
sequence.cpp:70:27: warning: division by zero [-Wdiv-by-zero]
   70 |   if(num>=200*MAXN)cout<<1/0;
      |                          ~^~
sequence.cpp: In function 'int solve(int)':
sequence.cpp:111:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |  for(int ii=0;ii<poss[val].size();ii++){
      |               ~~^~~~~~~~~~~~~~~~~
sequence.cpp:112:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |   for(int ff=ii;ff<poss[val].size();ff++){
      |                 ~~^~~~~~~~~~~~~~~~~

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