Submission #1041929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041929		PM1	ZIGZAG (INOI20_zigzag)	C++17	0 / 100	721 ms	75976 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
#define ll long long
const int mxn=3e5+5,szz=(1<<20);
int n,q,a[mxn];
bool aval=0;
ll akhar,fakhar,bakhar,ans;
struct segment{
	ll res[szz],rast[szz],chap[szz],lazysum[szz],lazy[szz],brast[szz],bchap[szz],frast[szz],fchap[szz];
	void getm(int id,int L,int R){
		if(!aval){
			aval=1;
			akhar=rast[id];
			bakhar=brast[id];
			fakhar=frast[id];
			ans=res[id];
		}
		else{
			int cnt=0;
			//cout<<akhar<<" "<<chap[id]<<'\n';
			if(fakhar<=akhar && akhar>chap[id] && chap[id]<=fchap[id]){
				ans+=bakhar*bchap[id];
				if(brast[id]==R-L)
					cnt=1;
			}
			if(fakhar>=akhar && akhar<chap[id] && chap[id]>=fchap[id]){
				ans+=bakhar*bchap[id];
				if(brast[id]==R-L)
					cnt=1;
			}
			akhar=rast[id];
			fakhar=(R-L==1)?akhar:frast[id];
			ans+=res[id];
			bakhar=(cnt)?bakhar+brast[id]:brast[id];
		}

	}
	void shift(int id){
		for(int x=id*2;x<=id*2+1;x++){
			rast[x]*=(lazy[id])?-1:1;
			chap[x]*=(lazy[id])?-1:1;
			rast[x]+=lazysum[id];
			chap[x]+=lazysum[id];
			frast[x]*=(lazy[id])?-1:1;
			fchap[x]*=(lazy[id])?-1:1;
			frast[x]+=lazysum[id];
			fchap[x]+=lazysum[id];
			lazysum[x]*=(lazy[id])?-1:1;
			lazysum[x]+=lazysum[id];
			lazy[x]^=lazy[id];
		}

		lazysum[id]=lazy[id]=0;
	}
	void merge(int id,int L,int R,int mid){
		rast[id]=rast[id*2+1];
		chap[id]=chap[id*2];
		frast[id]=(R-mid==1)?rast[id*2]:frast[id*2+1];
		fchap[id]=(mid-L==1)?chap[id*2+1]:fchap[id*2];
		res[id]=res[id*2]+res[id*2+1];
		brast[id]=brast[id*2+1];
		bchap[id]=bchap[id*2];
		if(frast[id*2]<=rast[id*2] && rast[id*2]>chap[id*2+1] && chap[id*2+1]<=fchap[id*2+1]){
			res[id]+=brast[id*2]*bchap[id*2+1];
			if(brast[id*2+1]==R-mid)
				brast[id]+=brast[id*2];
			if(bchap[id*2]==mid-L)
				bchap[id]+=bchap[id*2+1];
		}
		if(frast[id*2]>=rast[id*2] && rast[id*2]<chap[id*2+1] && chap[id*2+1]>=fchap[id*2+1]){
			res[id]+=brast[id*2]*bchap[id*2+1];
			if(brast[id*2+1]==R-mid)
				brast[id]+=brast[id*2];
			if(bchap[id*2]==mid-L)
				bchap[id]+=bchap[id*2+1];
		}
	}
	void add(int id,int L,int R,int l,int r,int x){
		if(l>=R || L>=r)
			return ;
		if(l<=L && R<=r){
			lazysum[id]+=x;
			rast[id]+=x;
			chap[id]+=x;
			frast[id]+=x;
			fchap[id]+=x;
			if(L+1==R){
				brast[id]=bchap[id]=1;
				res[id]=1;
			}
			return ;
		}
		int mid=(L+R)>>1;
		shift(id);
		add(id*2,L,mid,l,r,x);
		add(id*2+1,mid ,R,l,r,x);
		merge(id,L,R,mid);
		return ;
	}
	void up(int id,int L,int R,int l,int r){
		if(l>=R || L>=r)
			return ;
		if(l<=L && R<=r){
			lazysum[id]*=-1;
			rast[id]*=-1;
			chap[id]*=-1;
			frast[id]*=-1;
			fchap[id]*=-1;
			lazy[id]^=1;
			return ;
		}
		int mid=(L+R)>>1;
		shift(id);
		up(id*2,L,mid,l,r);
		up(id*2+1,mid, R,l,r);
		merge(id,L,R,mid);
		return ;
	}
	void get(int id,int L,int R,int l,int r){
		if(l>=R || L>=r)
			return ;
		if(l<=L && R<=r){
			getm(id,L,R);
			return ;
		}
		int mid=(L+R)>>1;
		shift(id);
		get(id*2,L,mid,l,r);
		get(id*2+1,mid, R,l,r);
		merge(id,L,R,mid);
		return ;
	}
}seg;
int main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		seg.add(1,1,n+1,i,i+1,a[i]);
	}
	while(q--){
		int l,r,z;
		char ty;
		cin>>ty;
		if(ty=='\\')
			cin>>ty;
		cin>>l>>r;
		if(ty=='+'){
			cin>>z;
			seg.add(1,1,n+1,l,r+1,z);
		}
		else if(ty=='?'){
			aval=0;
			seg.get(1,1,n+1,l,r+1);
			cout<<ans<<'\n';
		}
		else{
			seg.up(1,1,n+1,l,r+1);
		}
	}
	return 0;
}

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