Submission #634209

#	Time	Username	Problem	Language	Result	Execution time	Memory
634209		S2speed	ZIGZAG (INOI20_zigzag)	C++17	100 / 100	896 ms	94100 KiB

Main

#include<bits/stdc++.h>

using namespace std;

#pragma GCC optimize("Ofast")

#define sze(x) (ll)(x.size())
typedef long long ll;

const ll maxn = 3e5 + 17;

struct node {

	ll ans , p0 , p1 , s0 , s1 , l , fr , ls;

	void def(){
		ans = p0 = p1 = s0 = s1 = l = 0;
		return;
	}

	void init(ll x){
		ans = l = p0 = p1 = s0 = s1 = 1;
		fr = ls = x;
		return;
	}

	friend node operator + (node a , node b){
		node res;
		if(a.l == 0) return b;
		if(b.l == 0) return a;
		res.l = a.l + b.l;
		res.fr = a.fr; res.ls = b.ls;
		res.ans = a.ans + b.ans;
		if(a.ls < b.fr){
			res.ans += a.s0 * b.p1;
		}
		if(a.ls > b.fr){
			res.ans += a.s1 * b.p0;
		}
		if(b.l & 1){
			if(b.s0 == b.l && a.ls > b.fr){
				res.s0 = b.l + a.s1;
			} else {
				res.s0 = b.s0;
			}
			if(b.s1 == b.l && a.ls < b.fr){
				res.s1 = b.l + a.s0;
			} else {
				res.s1 = b.s1;
			}
		} else {
			if(b.s0 == b.l && a.ls < b.fr){
				res.s0 = b.l + a.s0;
			} else {
				res.s0 = b.s0;
			}
			if(b.s1 == b.l && a.ls > b.fr){
				res.s1 = b.l + a.s1;
			} else {
				res.s1 = b.s1;
			}
		}
		if(a.l & 1){
			if(a.p0 == a.l && b.fr > a.ls){
				res.p0 = a.l + b.p1;
			} else {
				res.p0 = a.p0;
			}
			if(a.p1 == a.l && b.fr < a.ls){
				res.p1 = a.l + b.p0;
			} else {
				res.p1 = a.p1;
			}
		} else {
			if(a.p0 == a.l && b.fr < a.ls){
				res.p0 = a.l + b.p0;
			} else {
				res.p0 = a.p0;
			}
			if(a.p1 == a.l && b.fr > a.ls){
				res.p1 = a.l + b.p1;
			} else {
				res.p1 = a.p1;
			}
		}
		return res;
	}

	void rev(){
		swap(p0 , p1); swap(s0 , s1);
		ls = -ls; fr = -fr;
		return;
	}

	friend void operator += (node &a , ll k){
		a.ls += k; a.fr += k;
		return;
	}

};

struct segtree {

	ll sz = 1;
	vector<node> val;
	vector<ll> laz , raz;
	node def;

	void init(ll n){
		while(sz < n) sz <<= 1;
		def.def();
		val.assign(sz << 1 , def);
		laz.assign(sz << 1 , 0); raz.assign(sz << 1 , 0);
		return;
	}

	void build(vector<ll> &a , ll x , ll lx , ll rx){
		if(rx - lx == 1){
			if(lx < sze(a)){
				val[x].init(a[lx]);
			}
			return;
		}
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		build(a , ln , lx , m); build(a , rn , m , rx);
		val[x] = val[ln] + val[rn];
		return;
	}

	void build(vector<ll> &a){
		build(a , 0 , 0 , sz);
		return;
	}

	void shift(ll x , ll lx , ll rx){
		ll h = laz[x] , c = raz[x];
		laz[x] = raz[x] = 0;
		val[x] += h;
		if(c) val[x].rev();
		if(rx - lx == 1) return;
		ll ln = (x << 1) + 1 , rn = ln + 1;
		if(raz[ln]) laz[ln] -= h;
		else laz[ln] += h;
		if(raz[rn]) laz[rn] -= h;
		else laz[rn] += h;
		raz[ln] ^= c; raz[rn] ^= c;
		return;
	}

	void add(ll l , ll r , ll k , ll x , ll lx , ll rx){
		shift(x , lx , rx);
		if(rx <= l || lx >= r) return;
		if(rx <= r && lx >= l){
//			cout<<lx<<' '<<rx<<' '<<k<<'\n';
			laz[x] = k;
			shift(x , lx , rx);
			return;
		}
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		add(l , r , k , ln , lx , m); add(l , r , k , rn , m , rx);
		val[x] = val[ln] + val[rn];
		return;
	}

	void add(ll l , ll r , ll k){
		add(l , r , k , 0 , 0 , sz);
		return;
	}

	void rev(ll l , ll r , ll x , ll lx , ll rx){
		shift(x , lx , rx);
		if(rx <= l || lx >= r) return;
		if(rx <= r && lx >= l){
//			cout<<lx<<' '<<rx<<'\n';
			raz[x] = 1;
			shift(x , lx , rx);
			return;
		}
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		rev(l , r , ln , lx , m); rev(l , r , rn , m , rx);
		val[x] = val[ln] + val[rn];
		return;
	}

	void rev(ll l , ll r){
		rev(l , r , 0 , 0 , sz);
		return;
	}

	node cal(ll l , ll r , ll x , ll lx , ll rx){
		shift(x , lx , rx);
		if(rx <= l || lx >= r) return def;
		if(rx <= r && lx >= l) return val[x];
		ll m = (rx + lx) >> 1 , ln = (x << 1) + 1 , rn = ln + 1;
		node a = cal(l , r , ln , lx , m) , b = cal(l , r , rn , m , rx);
		return a + b;
	}

	ll cal(ll l , ll r){
		node h = cal(l , r , 0 , 0 , sz);
		return h.ans;
	}

};

segtree st;
vector<ll> a;

int main(){
	ios_base::sync_with_stdio(false); cout.tie(0); cin.tie(0);

	ll n , q;
	cin>>n>>q;
	st.init(n); a.resize(n);
	for(ll i = 0 ; i < n ; i++){
		cin>>a[i];
	}
	st.build(a);
	for(ll e = 0 ; e < q ; e++){
		char c;
		ll l , r;
		cin>>c>>l>>r; l--;
		if(c == '*'){
			st.rev(l , r);
		} else if(c == '+'){
			ll k;
			cin>>k;
			st.add(l , r , k);
		} else {
			cout<<st.cal(l , r)<<'\n';
		}
	}
	return 0;
}

/*
6 4
2 3 4 2 3 5
+ 3 6 -5
* 4 6
+ 5 5 1
? 1 6
*/

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