Submission #768689

#	Time	Username	Problem	Language	Result	Execution time	Memory
768689		amirhoseinfar1385	ZIGZAG (INOI20_zigzag)	C++17	100 / 100	1429 ms	99948 KiB

Main

#include<bits/stdc++.h>
using namespace std;
long long n,q;
long long kaf=(1<<19);
struct segment{
	struct node{
		long long sum,len,lazy,lazysum;
		node(){
			lazy=sum=len=lazysum=0;
		}
	};
	node seg[(1<<20)];
	void build(long long i){
		if(i>=kaf){
			seg[i].len=1;
			return ;
		}
		build((i<<1));
		build((i<<1)^1);
		seg[i].len=seg[(i<<1)].len;
		seg[i].len=seg[(i<<1)^1].len;
		return ;
	}

	void calc(long long i){
		if(i>=kaf){
			seg[i].sum+=seg[i].lazysum;
			seg[i].lazysum=0;
			if(seg[i].lazy==1){
				seg[i].lazy=0;
				seg[i].sum=-seg[i].sum;
			}
			return;
		}
		long long fake=seg[(i<<1)].sum+seg[(i<<1)].lazysum*seg[(i<<1)].len;
		if(seg[(i<<1)].lazy==1){
			fake=-fake;
		}
		seg[i].sum=fake;
		fake=seg[(i<<1)^1].sum+seg[(i<<1)^1].lazysum*seg[(i<<1)^1].len;
		if(seg[(i<<1)^1].lazy==1){
			fake=-fake;
		}
		seg[i].sum+=fake;
	}

	void shift(long long i){
		if(i>=kaf){
			return calc(i);
		}
		if(seg[i].lazysum==0&&seg[i].lazy==0){
			return ;
		}
		if(seg[i].lazy==1){
			seg[i].lazysum*=-1;
			seg[(i<<1)].lazy^=1;
			seg[(i<<1)^1].lazy^=1;
			seg[i].lazy=0;
		}
		if(seg[(i<<1)].lazy==1){
			seg[(i<<1)].lazysum-=seg[i].lazysum;
		}
		else{
			seg[(i<<1)].lazysum+=seg[i].lazysum;
		}
		if(seg[(i<<1)^1].lazy==1){
			seg[(i<<1)^1].lazysum-=seg[i].lazysum;
		}
		else{
			seg[(i<<1)^1].lazysum+=seg[i].lazysum;
		}
		seg[i].lazysum=0;
	}

	void updsum(long long i,long long l,long long r,long long tl,long long tr,long long w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			if(seg[i].lazy==1){
				seg[i].lazysum-=w;
				return ;
			}
			seg[i].lazysum+=w;
			return ;
		}
		shift(i);
		long long m=(l+r)>>1;
		updsum((i<<1),l,m,tl,tr,w);
		updsum((i<<1)^1,m+1,r,tl,tr,w);
		calc(i);
	}

	void updmanf(long long i,long long l,long long r,long long tl,long long tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			seg[i].lazy^=1;
			return ;
		}
		shift(i);
		long long m=(l+r)>>1;
		updmanf((i<<1),l,m,tl,tr);
		updmanf((i<<1)^1,m+1,r,tl,tr);
		calc(i);
	}

	long long pors(long long i,long long l,long long r,long long tl,long long tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return 0;
		}
		shift(i);
		calc(i);
		if(l>=tl&&r<=tr){
			if(l==r){
				return seg[i].sum;
			}
			long long ret=seg[i].sum+seg[i].lazysum*seg[i].len;
			if(seg[i].lazy==1){
				ret=-ret;
			}
			return ret;
		}
		long long m=(l+r)>>1;
		long long ret=pors((i<<1),l,m,tl,tr)+pors((i<<1)^1,m+1,r,tl,tr);
		return ret;
	}
}seg;

struct segr{
	struct node{
		long long res,av,akh,tedav,tedakh,ted,lazy;
		node(){
			res=ted=av=akh=tedav=tedakh=lazy=0;
		}
	};
	node seg[(1<<20)];
	void build(long long i){
		if(i>=kaf){
			seg[i].ted=1;
			return ;
		}
		build((i<<1));
		build((i<<1)^1);
		seg[i].ted+=seg[(i<<1)].ted;
		seg[i].ted+=seg[(i<<1)^1].ted;
	}
	node merge(node a,node b){
		if(a.ted==0){
			return b;
		}
		if(b.ted==0){
			return a;
		}
		if(a.lazy==1){
			a.av*=-1;
			a.akh*=-1;
		}
		if(b.lazy==1){
			b.av*=-1;
			b.akh*=-1;
		}
		node ret;
		ret.av=a.av;
		ret.akh=b.akh;
		ret.tedav=a.tedav;
		ret.tedakh=b.tedakh;
		if(a.tedav==a.ted&&b.av!=0&&b.av!=a.akh){
			ret.tedav+=b.tedav;
		}
		if(b.tedakh==b.ted&&a.akh!=0&&b.av!=a.akh){
			ret.tedakh+=a.tedakh;
		}
		ret.lazy=0;
		ret.ted=a.ted+b.ted;
		ret.res=a.res+b.res;
		if(a.akh!=b.av){
			ret.res+=a.tedakh*b.tedav;
		}
		return ret;
	}

	void calc(long long i){
		if(i>=kaf){
			if(seg[i].lazy==0){
				return ;
			}
			seg[i].lazy=0;
			seg[i].av*=-1;
			seg[i].akh*=-1;
			return ;
		}
		seg[i]=merge(seg[(i<<1)],seg[(i<<1)^1]);
	}

	void shift(long long i){
		if(i>=kaf){
			return calc(i);
		}
		if(seg[i].lazy==0){
			return ;
		}
		seg[(i<<1)].lazy^=1;
		seg[(i<<1)^1].lazy^=1;
		seg[i].lazy=0;
		return ;
	}

	void ins(long long i,long long l,long long r,long long tl,long long tr,long long w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			//cout<<l<<" "<<r<<" "<<w<<"\n";
			seg[i].lazy=0;
			seg[i].av=seg[i].akh=w;
			if(w!=0){
				seg[i].res=seg[i].tedav=seg[i].tedakh=seg[i].ted=1;
			}
			else{
				seg[i].res=seg[i].tedav=seg[i].tedakh=0;
				seg[i].ted=1;
			}
			return ;
		}
		shift(i);
		long long m=(l+r)>>1;
		ins((i<<1),l,m,tl,tr,w);
		ins((i<<1)^1,m+1,r,tl,tr,w);
		calc(i);
	}
	void updmanf(long long i,long long l,long long r,long long tl,long long tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			seg[i].lazy^=1;
			return ;
		}
		shift(i);
		long long m=(l+r)>>1;
		updmanf((i<<1),l,m,tl,tr);
		updmanf((i<<1)^1,m+1,r,tl,tr);
		return calc(i);
	}
	node alak;
	node pors(long long i,long long l,long long r,long long tl,long long tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return alak;
		}
		shift(i);
		calc(i);
		if(l>=tl&&r<=tr){
			return seg[i];
		}
		long long m=(l+r)>>1;
		return merge(pors((i<<1),l,m,tl,tr),pors((i<<1)^1,m+1,r,tl,tr));
	}
	long long solve(long long l,long long r){
		return pors(1,0,kaf-1,l,r).res+r-l+2;
	}
}segres;


int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	long long last=0;
	seg.build(1);
	segres.build(1);
	for(long long i=1;i<=n;i++){
		long long d;
		cin>>d;
	//	cout<<i<<endl;
		seg.updsum(1,0,kaf-1,i,i,d);
	//	cout<<i<<endl;
		if(i>1){
			if(d<last){
				segres.ins(1,0,kaf-1,i-1,i-1,-1);
			}
			if(d==last){
				segres.ins(1,0,kaf-1,i-1,i-1,0);
			}
			if(d>last){
				segres.ins(1,0,kaf-1,i-1,i-1,1);
			}
		}
	//	cout<<i<<endl;
		last=d;
	}
	for(long long i=0;i<q;i++){
		char c;
		cin>>c;
		if(c=='?'){
			long long l,r;
			cin>>l>>r;
			cout<<segres.solve(l,r-1)<<"\n";
		}
		else if(c=='*'){
			long long vasl=0,vasr=0;
			long long l,r;
			cin>>l>>r;
			seg.updmanf(1,0,kaf-1,l,r);
			segres.updmanf(1,0,kaf-1,l,r-1);
			long long wl=seg.pors(1,0,kaf-1,l,l),wll=seg.pors(1,0,kaf-1,l-1,l-1),wr=seg.pors(1,0,kaf-1,r,r),wrr=seg.pors(1,0,kaf-1,r+1,r+1);
			if(wl>wll){
				vasl=1;
			}
			else if(wl==wll){
				vasl=0;
			}
			else{
				vasl=-1;
			}
			if(wrr>wr){
				vasr=1;
			}
			else if(wr==wrr){
				vasr=0;
			}
			else{
				vasr=-1;
			}
			if(l>1){
				segres.ins(1,0,kaf-1,l-1,l-1,vasl);
			}
			if(r<n){
				segres.ins(1,0,kaf-1,r,r,vasr);
			}
		}
		else{
			long long vasl=0,vasr=0;
			long long l,r,w;
			cin>>l>>r>>w;
			seg.updsum(1,0,kaf-1,l,r,w);
			long long wl=seg.pors(1,0,kaf-1,l,l),wll=seg.pors(1,0,kaf-1,l-1,l-1),wr=seg.pors(1,0,kaf-1,r,r),wrr=seg.pors(1,0,kaf-1,r+1,r+1);
			if(wl>wll){
				vasl=1;
			}
			else if(wl==wll){
				vasl=0;
			}
			else{
				vasl=-1;
			}
			if(wrr>wr){
				vasr=1;
			}
			else if(wr==wrr){
				vasr=0;
			}
			else{
				vasr=-1;
			}
			if(l>1){
				segres.ins(1,0,kaf-1,l-1,l-1,vasl);
			}
			if(r<n){
				segres.ins(1,0,kaf-1,r,r,vasr);
			}
		}
	}
}

• Subtask 1: 8 / 8
• Subtask 2: 42 / 42
• Subtask 3: 35 / 35
• Subtask 4: 15 / 15