Submission #749389

#	Time	Username	Problem	Language	Result	Execution time	Memory
749389		boyliguanhan	Sequence (APIO23_sequence)	C++17	100 / 100	1157 ms	89076 KiB

sequence

#include <bits/stdc++.h>
#include "sequence.h"
using namespace std;
struct qj{
	int l,r;
	friend qj operator+(qj a,qj b){
		a.l+=b.l;a.r+=b.r;
		return a;
	}
};
struct node{
	int l,r,sl,is;
	qj it,iq,h,q,t;
}p[2000005];
vector<int>wz[500005];
int res,n;
void upset(int x){
	p[x].t.l=p[x<<1].t.l+p[x<<1|1].t.l;
	p[x].t.r=p[x<<1].t.r+p[x<<1|1].t.r;
	p[x].q.l=min(p[x<<1].q.l,p[x<<1|1].q.l+p[x<<1].t.l);
	p[x].q.r=max(p[x<<1].q.r,p[x<<1|1].q.r+p[x<<1].t.r);
	p[x].h.l=min(p[x<<1|1].h.l,p[x<<1].h.l+p[x<<1|1].t.l);
	p[x].h.r=max(p[x<<1|1].h.r,p[x<<1].h.r+p[x<<1|1].t.r);
	p[x].sl=p[x<<1].sl+p[x<<1|1].sl;
}
void reset(int x,int l,int r){
	p[x].l=l,p[x].r=r;
	if(l==r){
		p[x].h.l=p[x].h.r=p[x].q.l=p[x].q.r=p[x].t.l=p[x].t.r=1;
		return;
	}
	int mid=l+r>>1;
	reset(x<<1,l,mid);
	reset(x<<1|1,mid+1,r);
	upset(x);
}
void sets(int x,int d,int sum){
	if(p[x].l==d&&p[x].r==d){
		if(sum){
			p[x].h.l=p[x].h.r=p[x].q.l=p[x].q.r=p[x].t.l=p[x].t.r=sum;
			p[x].sl=0;
		}else{
			p[x].h.l=p[x].q.l=p[x].t.l=-1;
			p[x].h.r=p[x].q.r=p[x].t.r=1;
			p[x].sl=1;
		}
		return;
	}
	int mid=p[x].l+p[x].r>>1;
	if(d<=mid)sets(x<<1,d,sum);
	else sets(x<<1|1,d,sum);
	upset(x);
}
void gx(int x,int sum){
	for(int i=0;i<wz[x].size();i++)sets(1,wz[x][i],sum);
}
qj gets1(int x,int d){
	if(d==0)return (qj){0,0};
	if(p[x].l==p[x].r){
		p[x].it=p[x].t;
		return p[x].t;
	}
	int mid=p[x].l+p[x].r>>1;
	qj res=(qj){0,0};
	if(d<=mid){
		qj nww=gets1(x<<1,d);
		p[x].it=p[x<<1].it;
		return nww;
	}else{
		qj rr=gets1(x<<1|1,d);
		res.l=min(rr.l,p[x<<1|1].it.l+p[x<<1].h.l);
		res.r=max(rr.r,p[x<<1|1].it.r+p[x<<1].h.r);
		p[x].it=p[x<<1].t+p[x<<1|1].it;
	}
	return res;
}
void init(int x,int d){
	if(p[x].l==p[x].r){
		p[x].it=p[x].t,p[x].iq=p[x].q,p[x].is=p[x].sl;
		return;
	}
	if(p[x<<1].r<d){
		init(x<<1|1,d);
		p[x].it=p[x<<1|1].it,p[x].iq=p[x<<1|1].iq,p[x].is=p[x<<1|1].is;
		return;
	}
	init(x<<1,d);
	p[x].it=p[x<<1].it+p[x<<1|1].t;
	p[x].iq.l=min(p[x<<1].iq.l,p[x<<1|1].q.l+p[x<<1].it.l);
	p[x].iq.r=max(p[x<<1].iq.r,p[x<<1|1].q.r+p[x<<1].it.r);
	p[x].is=p[x<<1].is+p[x<<1|1].sl;
}
int gets(int x,int d,qj sum,int ans,int xy){
	if(p[x].l==p[x].r)return ans+p[x].sl;
	int mid=p[x].l+p[x].r>>1;
	if(d>mid)return gets(x<<1|1,d,sum,ans,1);
	if(xy){
		qj rt=p[x<<1].it+p[x<<1|1].q+sum;
		if(rt.l<=0&&rt.r>=0)return gets(x<<1|1,d,sum+p[x<<1].it,ans+p[x<<1].is,0);
		else return gets(x<<1,d,sum,ans,1);
	}else{
		qj rt=p[x<<1].t+p[x<<1|1].q+sum;
		if(rt.l<=0&&rt.r>=0)return gets(x<<1|1,d,sum+p[x<<1].t,ans+p[x<<1].sl,0);
		else return gets(x<<1,d,sum,ans,0);
	}
}
int sol(int x){
	qj fw=gets1(1,x-1);
	fw.l=min(0,fw.l),fw.r=max(fw.r,0);
	init(1,x);
	return gets(1,x,fw,0,1);
}
int solve(int x){
	int ans=0;
	for(int i=0;i<wz[x].size();i++){
		ans=max(ans,sol(wz[x][i]));
	}
	return ans;
}
int sequence(int N,vector<int>w){
	n=N;
	reset(1,1,n);
	for(int i=0;i<n;i++){
		wz[w[i]].push_back(i+1);
	}
	for(int i=1;i<=n;i++){
		gx(i-1,-1);
		gx(i,0);
		gx(i+1,1);
		res=max(res,solve(i));
	}
	return res;
}

Compilation message (stderr)

sequence.cpp: In function 'void reset(int, int, int)':
sequence.cpp:32:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |  int mid=l+r>>1;
      |          ~^~
sequence.cpp: In function 'void sets(int, int, int)':
sequence.cpp:49:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |  int mid=p[x].l+p[x].r>>1;
      |          ~~~~~~^~~~~~~
sequence.cpp: In function 'void gx(int, int)':
sequence.cpp:55:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for(int i=0;i<wz[x].size();i++)sets(1,wz[x][i],sum);
      |              ~^~~~~~~~~~~~~
sequence.cpp: In function 'qj gets1(int, int)':
sequence.cpp:63:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |  int mid=p[x].l+p[x].r>>1;
      |          ~~~~~~^~~~~~~
sequence.cpp: In function 'int gets(int, int, qj, int, int)':
sequence.cpp:95:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   95 |  int mid=p[x].l+p[x].r>>1;
      |          ~~~~~~^~~~~~~
sequence.cpp: In function 'int solve(int)':
sequence.cpp:115:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |  for(int i=0;i<wz[x].size();i++){
      |              ~^~~~~~~~~~~~~

• 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