Submission #1093434

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093434		alexander707070	Sequence (APIO23_sequence)	C++17	28 / 100	2044 ms	57036 KiB

sequence

#include<bits/stdc++.h>
 
#define MAXN 500007
using namespace std;
 
int n,a[MAXN],ans,c[MAXN];
 
vector<int> poss[MAXN];

struct node{
	int sum;
	int minpref,maxpref;
	int minsuff,maxsuff;
 
	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),
		min(sc.minsuff,sc.sum+fr.minsuff),max(sc.maxsuff,sc.sum+fr.maxsuff)};
	}
}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;
			
			if(val==1)tree[v].minpref=0;
			else tree[v].minpref=-1;

			if(val==-1)tree[v].maxpref=0;
			else tree[v].maxpref=1;

			if(val==1)tree[v].minsuff=0;
			else tree[v].minsuff=-1;

			if(val==-1)tree[v].maxsuff=0;
			else tree[v].maxsuff=1;

		}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,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;
 
bool solve(int val,int len){
 
	for(int ii=0;ii+len-1<poss[val].size();ii++){
		int ff=ii+len-1;

		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+1,n);
		int minpref=curr.minpref,maxpref=curr.maxpref;

		curr=seg.getinfo(1,1,n,1,i-1);
		int minsuff=curr.minsuff,maxsuff=curr.maxsuff;

		if((ff-ii+1)>=sum+minpref+minsuff and (ff-ii+1)>=-sum-maxpref-maxsuff)return true;
	}
 
	return false;
}
 
bool check(int len){
	for(int i=1;i<=n;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(solve(i,len))return true;
	}
	return false;
}
 
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);
	}

	int l=1,r=n+1,tt;
	while(l+1<r){
		tt=(l+r)/2;
		if(check(tt)){
			l=tt;
		}else{
			r=tt;
		}
	}

	if(check(l+4))l+=4;
	if(check(l+3))l+=3;
	if(check(l+2))l+=2;
	if(check(l+1))l++;

	return l;
}
 
/*int main(){

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

Compilation message (stderr)

sequence.cpp: In function 'bool solve(int, int)':
sequence.cpp:62:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for(int ii=0;ii+len-1<poss[val].size();ii++){
      |               ~~~~~~~~^~~~~~~~~~~~~~~~~

• 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