답안 #1042055

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1042055 2024-08-02T13:33:45 Z PM1 ZIGZAG (INOI20_zigzag) C++17
42 / 100
816 ms 84424 KB
#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(akhar>chap[id]){
				if(fakhar<=akhar && chap[id]<=fchap[id]){
					ans+=bakhar*bchap[id];
					if(brast[id]==R-L)
						cnt=1;
				}
				else if(fakhar<=akhar){
					ans+=bakhar;
				}
				else if(chap[id]<=fchap[id]){
					ans+=bchap[id];
					if(brast[id]==R-L)
						cnt=2;
				}
			}
			if(akhar<chap[id]){
				if(fakhar>=akhar && chap[id]>=fchap[id]){
					ans+=bakhar*bchap[id];
					if(brast[id]==R-L)
						cnt=1;
				}
				else if(fakhar>=akhar){
					ans+=bakhar;
				}
				else if(chap[id]>=fchap[id]){
					ans+=bchap[id];
					if(brast[id]==R-L)
						cnt=2;
				}
			}
			fakhar=(R-L==1)?akhar:frast[id];
			akhar=rast[id];
			ans+=res[id];
			bakhar=(cnt==1)?bakhar+brast[id]:brast[id];
			if(cnt==2)
				bakhar++;
			
		}

	}
	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(rast[id*2]>chap[id*2+1]){
			//cout<<chap[id*2+1]<<" "<<fchap[id*2+1]<<'\n';
			if(frast[id*2]<=rast[id*2] && 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];
			}
			else if(frast[id*2]<=rast[id*2]){
				res[id]+=brast[id*2];
				if(bchap[id*2]==mid-L)
					bchap[id]++;
			}
		  	else if(chap[id*2+1]<=fchap[id*2+1]){
				res[id]+=bchap[id*2+1];
				if(brast[id*2+1]==R-mid)
					brast[id]++;
			}
			else
				res[id]++;
			//cout<<" "<<L<<" "<<R<<"" <<res[id]<<''
		}
		else if(rast[id*2]<chap[id*2+1]){
			if(frast[id*2]>=rast[id*2] && 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];
			}
			else if(frast[id*2]>=rast[id*2]){
				res[id]+=brast[id*2];
				if(bchap[id*2]==mid-L)
					bchap[id]++;
			}
		  	else if(chap[id*2+1]>=fchap[id*2+1]){
				res[id]+=bchap[id*2+1];
				if(brast[id*2+1]==R-mid)
					brast[id]++;
			}
			else
				res[id]++;
		}
	}
	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;
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 7516 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 712 ms 79188 KB Output is correct
2 Correct 159 ms 8784 KB Output is correct
3 Correct 702 ms 84304 KB Output is correct
4 Correct 816 ms 84332 KB Output is correct
5 Correct 697 ms 84304 KB Output is correct
6 Correct 731 ms 84324 KB Output is correct
7 Correct 714 ms 81140 KB Output is correct
8 Correct 747 ms 84308 KB Output is correct
9 Correct 695 ms 84424 KB Output is correct
10 Correct 615 ms 84404 KB Output is correct
11 Correct 707 ms 84392 KB Output is correct
12 Correct 759 ms 84260 KB Output is correct
13 Correct 594 ms 84304 KB Output is correct
14 Correct 580 ms 84304 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 7516 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 7516 KB Output isn't correct
2 Halted 0 ms 0 KB -