제출 #1134712

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1134712		bpptidp	Simple (info1cup19_simple)	C++20	100 / 100	338 ms	33928 KiB

subway

#include<bits/stdc++.h>
using namespace std;

#define int long long

int n;
struct{int lz=0,mxE=0,mxO=0,mnE=0,mnO=0,brp=0,brnp=0;}st[(int)8e5+4];

void add(int i,int x){
	st[i].lz+=x;
	if(x&1^1){//dodajem parnog
		if(!st[i].brp){//samo neparni
			st[i].mnO+=x;
			st[i].mxO+=x;
			return;
		}
		if(!st[i].brnp){//samo parni
			st[i].mxE+=x;
			st[i].mnE+=x;
			return;
		}
		//imam oba
		st[i].mnO+=x;
		st[i].mxO+=x;
		st[i].mxE+=x;
		st[i].mnE+=x;
		//ne menjam parnost pa brp i brnp ostaju isti
	}else{//dodajem neparnog
		if(!st[i].brp){//samo neparni
			st[i].mnE=st[i].mnO+x;
			st[i].mxE=st[i].mxO+x;
			st[i].mnO=st[i].mxO=0;
			swap(st[i].brp,st[i].brnp);
			return;
		}
		if(!st[i].brnp){//samo parni
			st[i].mnO=st[i].mnE+x;
			st[i].mxO=st[i].mxE+x;
			st[i].mnE=st[i].mxE=0;
			swap(st[i].brp,st[i].brnp);
			return;
		}
		//imam oba
		int mne=st[i].mnE,mxe=st[i].mxE;
		st[i].mnE=st[i].mnO+x;
		st[i].mxE=st[i].mxO+x;
		st[i].mnO=mne+x;
		st[i].mxO=mxe+x;
		swap(st[i].brp,st[i].brnp);
	}
}

void spadd(int i,int x){
	if(x&1)st[i].mnO=st[i].mxO=x;
	else st[i].mnE=st[i].mxE=x;
}

void push(int i){
	if(!st[i].lz)return;
	add(i*2,st[i].lz);
	add(i*2+1,st[i].lz);
	st[i].lz=0;
}

int ff(int&x,int&y){
	if(!x)return y;
	if(!y)return x;
	return min(x,y);
}

void upd(int l,int r,int x,int i=1,int tl=1,int tr=n){
	if(tl>=l&&tr<=r){
		if(tl==tr&&!st[i].mnO&&!st[i].mnE){//na buildu
			st[i].brp=(x&1^1);
			st[i].brnp=(x&1);
			spadd(i,x);
			return;
		}

		add(i,x);
		return;
	}
	push(i);
	int mid=(tl+tr)/2;
	if(mid>=l)upd(l,r,x,i*2,tl,mid);
	if(mid+1<=r)upd(l,r,x,i*2+1,mid+1,tr);
	st[i].mxO=max(st[i*2].mxO,st[i*2+1].mxO);
	st[i].mxE=max(st[i*2].mxE,st[i*2+1].mxE);
	st[i].mnO=ff(st[i*2].mnO,st[i*2+1].mnO);
	st[i].mnE=ff(st[i*2].mnE,st[i*2+1].mnE);
	st[i].brp=st[i*2].brp+st[i*2+1].brp;
	st[i].brnp=st[i*2].brnp+st[i*2+1].brnp;
}

array<int,2>qry(int l,int r,int i=1,int tl=1,int tr=n){
	if(tl>=l&&tr<=r)return{st[i].mnE,st[i].mxO};
	push(i);
	int mid=(tl+tr)/2;
	array<int,2>ret={(int)2e18,-(int)2e18};
	if(mid>=l){
		array<int,2>q=qry(l,r,i*2,tl,mid);
		if(!q[0])q[0]=2e18;
		ret[0]=min(ret[0],q[0]);
		if(!q[1])q[1]=-2e18;
		ret[1]=max(ret[1],q[1]);
	}
	if(mid+1<=r){
		array<int,2>q=qry(l,r,i*2+1,mid+1,tr);
		if(!q[0])q[0]=2e18;
		ret[0]=min(ret[0],q[0]);
		if(!q[1])q[1]=-2e18;
		ret[1]=max(ret[1],q[1]);
	}
	return ret;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin>>n;
    if(n==1)cin>>n;

    for(int i=1,x;i<=n;++i){
    	cin>>x;
    	upd(i,i,x);
    }

    int q;
    cin>>q;

    while(q--){
    	int tp;
    	cin>>tp;
    	if(!tp){
    		int l,r,x;
    		cin>>l>>r>>x;
    		upd(l,r,x);
    	}else{
    		int l,r;
    		cin>>l>>r;
    		array<int,2>ans=qry(l,r);
    		if(!ans[0])ans[0]=2e18;
    		if(!ans[1])ans[1]=-2e18;
    		cout<<(ans[0]>=2e18?-1:ans[0])<<' '<<(ans[1]<=-2e18?-1:ans[1])<<'\n';
    	}
    }
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40