Submission #302382

#	Time	Username	Problem	Language	Result	Execution time	Memory
302382		errorgorn	Progression (NOI20_progression)	C++14	100 / 100	1733 ms	96632 KiB

Progression

#include <bits/stdc++.h>

using namespace std;



#define ll long long

#define ii pair<int,int>

#define fi first

#define se second

#define endl '\n'



#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);(s<e?x++:x--))

#define sz(x) (int) (x).size()

#define all(x) (x).begin(),(x).end()



const ll INF=1e18;



int arr[300010];



struct dat{

	ll ans;

	ll lval,llen;

	ll rval,rlen;

	ll l,r;

	

	dat(){

		llen=-1,rlen=-1;

	}

	

	dat(ll i,ll j,ll _l,ll _r){

		ans=j;

		lval=i;

		llen=j;

		rval=-1;

		rlen=-1;

		l=_l;

		r=_r;

	}

};



dat merge(dat i,dat j){

	dat res=dat();

	

	res.l=i.l,res.r=j.r;

	res.ans=max(i.ans,j.ans);

	

	ll temp=j.l-i.r;

	

	if (i.llen==-1){

		res.llen=1;

		res.lval=temp;

	}

	else if (i.rlen==-1){

		if (i.lval==temp){

			res.llen=i.llen+1;

			res.lval=temp;

		}

		else{

			res.llen=i.llen;

			res.lval=i.lval;

			res.rlen=1;

			res.rval=temp;

		}

	}

	else{

		if (i.rval==temp){

			res.llen=i.llen;

			res.lval=i.lval;

			res.rlen=i.rlen+1;

			res.rval=temp;

		}

		else{

			res.llen=i.llen;

			res.lval=i.lval;

			res.rlen=1;

			res.rval=temp;

		}

	}

	

	res.ans=max(res.ans,max(res.llen,res.rlen));

	

	if (j.llen!=-1){

		if (res.rlen==-1){

			if (res.lval==j.lval) res.llen+=j.llen;

			else{

				res.rlen=j.llen;

				res.rval=j.lval;

			}

		}

		else{

			if (res.rval==j.lval) res.rlen+=j.llen;

			else{

				res.rlen=j.llen;

				res.rval=j.lval;

			}

		}

	}

	

	res.ans=max(res.ans,max(res.llen,res.rlen));

	

	if (j.rlen!=-1){

		res.rlen=j.rlen;

		res.rval=j.rval;

	}

	

	res.ans=max(res.ans,max(res.llen,res.rlen));

	

	return res;

}



struct node{

	ll s,e,m,len;

	dat val;

	ll incs=0,incc=0;

	ll sets=INF,setc=INF;

	node *l,*r;

	

	node (ll _s,ll _e){

		s=_s,e=_e,m=s+e>>1;

		len=e-s+1;

		

		if (s!=e){

			l=new node(s,m);

			r=new node(m+1,e);

			val=merge(l->val,r->val);

		}

		else{

			val=dat(-1,-1,arr[s],arr[s]);

		}

	}

	

	void propo(){

		if (sets!=INF){

			if (s==e) val=dat(-1,-1,sets,sets);

			else val=dat(setc,len-1,sets,sets+(len-1)*setc);

			

			if (s!=e){

				l->incs=l->incc=0;

				l->sets=sets,l->setc=setc;

				

				r->incs=r->incc=0;

				r->sets=sets+setc*l->len,r->setc=setc;

			}

			

			sets=INF;

			setc=INF;

		}

		

		if (incs || incc){

			val.l+=incs,val.r+=incs+(len-1)*incc;

			val.lval+=incc,val.rval+=incc;

			

			if (s!=e){

				l->incs+=incs,l->incc+=incc;

				

				r->incs+=incs+incc*l->len,r->incc+=incc;

			}

			

			incs=0;

			incc=0;

		}

	}

	

	void patch(ll i,ll j,ll S,ll C){

		propo();

		

		if (s==i && e==j) incs=S,incc=C;

		else{

			if (j<=m) l->patch(i,j,S,C);

			else if (m<i) r->patch(i,j,S,C);

			else l->patch(i,m,S,C),r->patch(m+1,j,S+(m-i+1)*C,C);

			

			l->propo(),r->propo();

			val=merge(l->val,r->val);

		}

	}

	

	void rewrite(ll i,ll j,ll S,ll C){

		propo();

		

		if (s==i && e==j) sets=S,setc=C;

		else{

			if (j<=m) l->rewrite(i,j,S,C);

			else if (m<i) r->rewrite(i,j,S,C);

			else l->rewrite(i,m,S,C),r->rewrite(m+1,j,S+(m-i+1)*C,C);

			

			l->propo(),r->propo();

			val=merge(l->val,r->val);

		}

	}

	

	dat query(ll i,ll j){

		propo();

		

		if (s==i && e==j) return val;

		else if (j<=m) return l->query(i,j);

		else if (m<i) return r->query(i,j);

		else return merge(l->query(i,m),r->query(m+1,j));

	}

	

	void print(){

		cout<<s<<" "<<e<<endl;

		cout<<val.llen<<" "<<val.lval<<" "<<val.rlen<<" "<<val.rval<<" "<<val.ans<<endl;

		

		if (s!=e){

			l->print();

			r->print();

		}

	}

} *root;



ll n,q;



int main(){

	cin.tie(0);

	cout.tie(0);

	ios::sync_with_stdio(false);

	

	cin>>n>>q;

	rep(x,1,n+1) cin>>arr[x];

	

	root=new node(0,300005);

	

	ll a,b,c,d;

	while (q--){

		cin>>a;

		

		if (a==1){

			cin>>a>>b>>c>>d;

			root->patch(a,b,c,d);

		}

		else if (a==2){

			cin>>a>>b>>c>>d;

			root->rewrite(a,b,c,d);

		}

		else{

			cin>>a>>b;

			if (a==b) cout<<1<<endl;

			else cout<<root->query(a,b).ans+1<<endl;

			

			//root->print();

		}

	}

	

	//rep(x,1,n+1) cout<<root->query(x,x).l<<" ";

}

Compilation message (stderr)

Progression.cpp: In constructor 'node::node(long long int, long long int)':
Progression.cpp:233:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  233 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~

• Subtask 1: 9 / 9
• Subtask 2: 15 / 15
• Subtask 3: 35 / 35
• Subtask 4: 11 / 11
• Subtask 5: 13 / 13
• Subtask 6: 17 / 17