oj.uz

Submission #768689

# Submission time Handle Problem Language Result Execution time Memory
768689 2023-06-28T12:01:28 Z amirhoseinfar1385 ZIGZAG (INOI20_zigzag) C++17
100 / 100
 1429 ms 99948 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 90596 KB Output is correct
2 Correct 48 ms 90720 KB Output is correct
3 Correct 49 ms 90572 KB Output is correct
4 Correct 50 ms 90660 KB Output is correct
5 Correct 57 ms 90672 KB Output is correct
6 Correct 39 ms 90612 KB Output is correct
7 Correct 47 ms 90648 KB Output is correct

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1199 ms 96264 KB Output is correct
2 Correct 296 ms 92780 KB Output is correct
3 Correct 1060 ms 99520 KB Output is correct
4 Correct 1211 ms 99416 KB Output is correct
5 Correct 1155 ms 99524 KB Output is correct
6 Correct 1217 ms 99504 KB Output is correct
7 Correct 1205 ms 96312 KB Output is correct
8 Correct 1214 ms 99408 KB Output is correct
9 Correct 1212 ms 99512 KB Output is correct
10 Correct 905 ms 99552 KB Output is correct
11 Correct 1098 ms 99516 KB Output is correct
12 Correct 1216 ms 99572 KB Output is correct
13 Correct 681 ms 99532 KB Output is correct
14 Correct 688 ms 99388 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 90596 KB Output is correct
2 Correct 48 ms 90720 KB Output is correct
3 Correct 49 ms 90572 KB Output is correct
4 Correct 50 ms 90660 KB Output is correct
5 Correct 57 ms 90672 KB Output is correct
6 Correct 39 ms 90612 KB Output is correct
7 Correct 47 ms 90648 KB Output is correct
8 Correct 402 ms 92484 KB Output is correct
9 Correct 404 ms 92472 KB Output is correct
10 Correct 467 ms 93504 KB Output is correct
11 Correct 269 ms 93132 KB Output is correct
12 Correct 394 ms 93500 KB Output is correct
13 Correct 472 ms 93392 KB Output is correct
14 Correct 425 ms 93424 KB Output is correct
15 Correct 418 ms 92500 KB Output is correct
16 Correct 435 ms 93428 KB Output is correct
17 Correct 394 ms 93640 KB Output is correct
18 Correct 255 ms 93428 KB Output is correct
19 Correct 254 ms 93396 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 90596 KB Output is correct
2 Correct 48 ms 90720 KB Output is correct
3 Correct 49 ms 90572 KB Output is correct
4 Correct 50 ms 90660 KB Output is correct
5 Correct 57 ms 90672 KB Output is correct
6 Correct 39 ms 90612 KB Output is correct
7 Correct 47 ms 90648 KB Output is correct
8 Correct 1199 ms 96264 KB Output is correct
9 Correct 296 ms 92780 KB Output is correct
10 Correct 1060 ms 99520 KB Output is correct
11 Correct 1211 ms 99416 KB Output is correct
12 Correct 1155 ms 99524 KB Output is correct
13 Correct 1217 ms 99504 KB Output is correct
14 Correct 1205 ms 96312 KB Output is correct
15 Correct 1214 ms 99408 KB Output is correct
16 Correct 1212 ms 99512 KB Output is correct
17 Correct 905 ms 99552 KB Output is correct
18 Correct 1098 ms 99516 KB Output is correct
19 Correct 1216 ms 99572 KB Output is correct
20 Correct 681 ms 99532 KB Output is correct
21 Correct 688 ms 99388 KB Output is correct
22 Correct 402 ms 92484 KB Output is correct
23 Correct 404 ms 92472 KB Output is correct
24 Correct 467 ms 93504 KB Output is correct
25 Correct 269 ms 93132 KB Output is correct
26 Correct 394 ms 93500 KB Output is correct
27 Correct 472 ms 93392 KB Output is correct
28 Correct 425 ms 93424 KB Output is correct
29 Correct 418 ms 92500 KB Output is correct
30 Correct 435 ms 93428 KB Output is correct
31 Correct 394 ms 93640 KB Output is correct
32 Correct 255 ms 93428 KB Output is correct
33 Correct 254 ms 93396 KB Output is correct
34 Correct 43 ms 90592 KB Output is correct
35 Correct 42 ms 90520 KB Output is correct
36 Correct 1399 ms 96640 KB Output is correct
37 Correct 1429 ms 99696 KB Output is correct
38 Correct 784 ms 98636 KB Output is correct
39 Correct 1405 ms 99848 KB Output is correct
40 Correct 1423 ms 96720 KB Output is correct
41 Correct 1294 ms 99808 KB Output is correct
42 Correct 1239 ms 96732 KB Output is correct
43 Correct 1339 ms 99736 KB Output is correct
44 Correct 1399 ms 99756 KB Output is correct
45 Correct 1401 ms 99748 KB Output is correct
46 Correct 1207 ms 99792 KB Output is correct
47 Correct 850 ms 99948 KB Output is correct