Submission #750410

#	Time	Username	Problem	Language	Result	Execution time	Memory
750410		jamezzz	Sequence (APIO23_sequence)	C++17	100 / 100	1591 ms	68020 KiB

sequence

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

#define pf printf
#define pb push_back

#define maxn 500005

struct node{
	int N,mn[maxn<<2],mx[maxn<<2],lz[maxn<<2];
	void ppo(int i,int s,int e){
		mx[i]+=lz[i];
		mn[i]+=lz[i];
		if(s!=e){
			lz[2*i+1]+=lz[i];
			lz[2*i+2]+=lz[i];
		}
		lz[i]=0;
	}
	void up(int i,int s,int e,int x,int y,int nv){
		if(s==x&&e==y){lz[i]+=nv;return;}
		int m=(s+e)>>1;
		if(y<=m)up(2*i+1,s,m,x,y,nv);
		else if(x>m)up(2*i+2,m+1,e,x,y,nv);
		else up(2*i+1,s,m,x,m,nv),up(2*i+2,m+1,e,m+1,y,nv);
		ppo(2*i+1,s,m);
		ppo(2*i+2,m+1,e);
		mn[i]=min(mn[2*i+1],mn[2*i+2]);
		mx[i]=max(mx[2*i+1],mx[2*i+2]);
	}
	inline void up(int x,int y,int nv){
		up(0,0,N,x,y,nv);
	}
	int qmx(int i,int s,int e,int x,int y){
		if(s==x&&e==y)return mx[i]+lz[i];
		ppo(i,s,e);
		int m=(s+e)>>1;
		if(y<=m)return qmx(2*i+1,s,m,x,y);
		if(x>m)return qmx(2*i+2,m+1,e,x,y);
		return max(qmx(2*i+1,s,m,x,m),qmx(2*i+2,m+1,e,m+1,y));
	}
	inline int qmx(int x,int y){
		return qmx(0,0,N,x,y);
	}
	int qmn(int i,int s,int e,int x,int y){
		if(s==x&&e==y)return mn[i]+lz[i];
		ppo(i,s,e);
		int m=(s+e)>>1;
		if(y<=m)return qmn(2*i+1,s,m,x,y);
		if(x>m)return qmn(2*i+2,m+1,e,x,y);
		return min(qmn(2*i+1,s,m,x,m),qmn(2*i+2,m+1,e,m+1,y));
	}
	inline int qmn(int x,int y){
		return qmn(0,0,N,x,y);
	}
}prt,srt;

int pmn[maxn],pmx[maxn],smn[maxn],smx[maxn],tot[maxn][2];
vector<int> v[maxn];

//a range is valid if sum(>=x)-sum(<x)>=0 --> find min: == x value 1
//and sum(>x)-sum(<=x)<=0 --> find max: == x value -1

inline bool check(int i,int l,int r){
	return (tot[i][0]-pmn[l]-smn[r]>=0)&&(tot[i][1]-pmx[l]-smx[r]<=0);
}

int sequence(int N,vector<int> A){
	prt.N=srt.N=N+1;
	for(int i=0;i<N;++i){
		v[A[i]].pb(i+1);
		prt.up(i+1,N+1,1);
		srt.up(0,i+1,1);
	}
	for(int i=1;i<=N;++i){
		for(int x:v[i]){
			pmn[x]=prt.qmn(0,x-1);
			smn[x]=srt.qmn(x+1,N+1);
		}
		tot[i][0]=prt.qmx(N,N);
		for(int x:v[i]){
			prt.up(x,N+1,-2);
			srt.up(0,x,-2);
		}
		tot[i][1]=prt.qmx(N,N);
		for(int x:v[i]){
			pmx[x]=prt.qmx(0,x-1);
			smx[x]=srt.qmx(x+1,N+1);
		}
	}
	int ans=0;
	for(int i=1;i<=N;++i){
		if(v[i].empty())continue;
		int l=0,r=0;
		while(r<v[i].size()){
			assert(l<=r);
			if(check(i,v[i][l],v[i][r])){
				ans=max(ans,r-l+1);
				++r;
			}
			else ++l;
		}
	}
	return ans;
}

Compilation message (stderr)

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:96:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |   while(r<v[i].size()){
      |         ~^~~~~~~~~~~~

• 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