Submission #1265805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265805		mhn_neek	ZIGZAG (INOI20_zigzag)	C++20	100 / 100	656 ms	94640 KiB

Main

// IN THE NAME OF GOD
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef pair<lli,lli> pii;
typedef vector<lli> ve;
typedef vector<pii> vp;
const lli N = 3e5 + 100;
const lli mod = 1e9+7;
const lli INF = 1e18;
#define PB push_back
#define MP make_pair
#define fi first
#define se second
#define debug(x) cerr<<(#x)<<" "<<x<<endl
#define FOR(x,y) for(lli x = 0; x < y ;x++)
#define FORS(x,y) for(lli x = 1; x <= y ;x++)
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(),x.end()
struct Node{
	lli lz =0 ;
	lli lzm= 1;
	lli  ans = 0;
	lli prf[2] = {0};
	lli suf[2] = {0};
	lli l= -1,r= -1;
	lli lef = 0,rig = 0;
};
Node seg[N<<2];
lli n,q;
lli A[N];




Node Tak(lli p){
	Node res;
	res.ans = 1;
	res.prf[0] = res.prf[1] = 1;
	res.suf[0] = res.suf[1] = 1;
	res.lz = 0;
	res.lzm = 1;
	res.l = p,res.r = p;
	res.lef = A[p];
	res.rig = A[p];
	return res;
}

bool deb = 0;

Node Merge(Node a,Node b){
	Node res;
	res.lz = 0,res.lzm = 1;
	res.l = a.l,res.r = b.r;
	/*debug(a.r);
	debug(a.lzm);
	debug(b.l);
	debug(b.lzm);*/
	res.lef = a.lef,res.rig = b.rig;
	lli L =a.rig;// A[a.r]*a.lzm + a.lz;
	lli R =b.lef;// A[b.l]*b.lzm + b.lz;

	lli sza = a.r-a.l+1,szb = b.r-b.l + 1;
	res.prf[0] = a.prf[0],res.prf[1] = a.prf[1];
	res.suf[0] = b.suf[0],res.suf[1] = b.suf[1];
	if(a.suf[0] == sza && L > R)
		res.prf[(sza%2)] = sza + b.prf[0];
	if(a.suf[1] == sza && L < R)
		res.prf[1-(sza%2)] = sza + b.prf[1];

	if(b.prf[0] == szb && L>R)
		res.suf[(szb%2)] = szb + a.suf[0];

	if(b.prf[1] == szb && L<R)
		res.suf[1-(szb%2)] = szb + a.suf[1];

	if(L<R)res.ans += a.suf[1]*b.prf[1];
	else if(L > R) res.ans += a.suf[0]*b.prf[0];
	res.ans += a.ans + b.ans;	
	
	return res;
}

void build(lli l = 1,lli r= n + 1,lli id = 1){
	if(r-l == 1){
		seg[id] = Tak(l);
		return;
	}
	lli mid = (l+r)/2;
	build(l,mid,id<<1);
	build(mid,r,(id<<1) + 1);
	seg[id] = Merge(seg[id<<1],seg[(id<<1) + 1]);
	/*
	debug(l);
	debug(r);
	debug(seg[id].ans);
	cerr<<endl<<endl;**/
}

void relax(lli id){
	seg[id*2].lzm *= seg[id].lzm;
	seg[id*2].lz *= seg[id].lzm;
	seg[id*2].lz += seg[id].lz;
	seg[id*2+1].lzm *= seg[id].lzm;
	seg[id*2+1].lz *= seg[id].lzm;
	seg[id*2+1].lz += seg[id].lz;
	if(seg[id].lzm == -1){
		swap(seg[id*2].prf[0],seg[id*2].prf[1]);	
		swap(seg[id*2].suf[0],seg[id*2].suf[1]);	
		swap(seg[id*2+1].prf[0],seg[id*2+1].prf[1]);	
		swap(seg[id*2+1].suf[0],seg[id*2+1].suf[1]);	
	}

	seg[id*2].lef*=seg[id].lzm;
	seg[id*2].lef +=seg[id].lz;
	seg[id*2].rig*=seg[id].lzm;
	seg[id*2].rig +=seg[id].lz;
	seg[id*2+1].lef*=seg[id].lzm;
	seg[id*2+1].lef +=seg[id].lz;
	seg[id*2+1].rig*=seg[id].lzm;
	seg[id*2+1].rig +=seg[id].lz;

	seg[id].lz = 0;
	seg[id].lzm = 1;
}

void Upd(lli l,lli r,lli st,lli en,lli typ,lli x,lli id){
	if(st >= r || en <= l)return;
	if(st <= l && en >= r){
		if(typ == 1){
			seg[id].lz += x;
			seg[id].lef += x;
			seg[id].rig += x;
		}else{
			swap(seg[id].prf[0],seg[id].prf[1]);	
			swap(seg[id].suf[0],seg[id].suf[1]);	

			seg[id].lzm *= -1;
			seg[id].lz *= -1;
			seg[id].lef *= -1;
			seg[id].rig *= -1;
		}
		return;
	}
	relax(id);
	lli mid=(l+r)/2;
	Upd(l,mid,st,en,typ,x,id<<1);
	Upd(mid,r,st,en,typ,x,(id<<1) + 1);
	seg[id] = Merge(seg[id<<1] ,seg[(id<<1) + 1]);
}
Node Get(lli l,lli r,lli st,lli en,lli id){
	if(st >= r  || en <= l){
		Node res;
		return res;
	}
	if( l>= st  && r <= en){
/*		debug(l);
		debug(r);
		debug(seg[id].l);
		debug(seg[id].r);
		debug(seg[id].ans);
*/		return seg[id];
	}
	relax(id);
	lli mid = (l + r)/2;
	if(mid>=en)return Get(l,mid,st,en,id<<1);
	if(mid <= st)return Get(mid,r,st,en,(id<<1) + 1);
/*	debug("--->");
	debug(l);
	debug(r);
	debug(st);
	debug(en);
	debug(mid);
	debug("---<");
	deb =1;
*/	Node res = Merge(Get(l,mid,st,en,id<<1),Get(mid,r,st,en,(id<<1) + 1));
	return res;

}






int main(){
	ios_base::sync_with_stdio(false);cin.tie(0),cout.tie(0);
	cin>>n>>q;
	FORS(i,n)cin>>A[i];
	build(1,n+1,1);/*
	debug(Get(1,n+1,1,2,1).ans);
	debug(Get(1,n+1,1,3,1).ans);
	exit(0);*/
	while(q--){
		char t;
		cin>>t;
		if(t == '?'){
			lli l,r;
			cin>>l>>r;
			cout<<Get(1,n+1,l,r+1,1).ans<<endl;
		}else if(t == '+'){
			lli l,r,x;
			cin>>l>>r>>x;
			Upd(1,n+1,l,r+1,1,x,1);
		}
		else{
			lli l,r;
			cin>>l>>r;
			Upd(1,n+1,l,r+1,0,-1,1);
		}
	}
}

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