oj.uz

Submission #634209

# Submission time Handle Problem Language Result Execution time Memory
634209 2022-08-24T05:56:22 Z S2speed ZIGZAG (INOI20_zigzag) C++17
100 / 100
 896 ms 94100 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1620 KB Output is correct
2 Correct 7 ms 1748 KB Output is correct
3 Correct 7 ms 1748 KB Output is correct
4 Correct 8 ms 1748 KB Output is correct
5 Correct 7 ms 1736 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 9 ms 1788 KB Output is correct

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 641 ms 85416 KB Output is correct
2 Correct 53 ms 2508 KB Output is correct
3 Correct 515 ms 93560 KB Output is correct
4 Correct 678 ms 93648 KB Output is correct
5 Correct 554 ms 93696 KB Output is correct
6 Correct 663 ms 93692 KB Output is correct
7 Correct 614 ms 90560 KB Output is correct
8 Correct 666 ms 93576 KB Output is correct
9 Correct 576 ms 93660 KB Output is correct
10 Correct 438 ms 93760 KB Output is correct
11 Correct 552 ms 93704 KB Output is correct
12 Correct 625 ms 93760 KB Output is correct
13 Correct 345 ms 93668 KB Output is correct
14 Correct 341 ms 93628 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1620 KB Output is correct
2 Correct 7 ms 1748 KB Output is correct
3 Correct 7 ms 1748 KB Output is correct
4 Correct 8 ms 1748 KB Output is correct
5 Correct 7 ms 1736 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 9 ms 1788 KB Output is correct
8 Correct 209 ms 23440 KB Output is correct
9 Correct 209 ms 23440 KB Output is correct
10 Correct 264 ms 24440 KB Output is correct
11 Correct 142 ms 24120 KB Output is correct
12 Correct 232 ms 24556 KB Output is correct
13 Correct 235 ms 24516 KB Output is correct
14 Correct 195 ms 24488 KB Output is correct
15 Correct 242 ms 23468 KB Output is correct
16 Correct 219 ms 24540 KB Output is correct
17 Correct 203 ms 24548 KB Output is correct
18 Correct 98 ms 24524 KB Output is correct
19 Correct 98 ms 24352 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1620 KB Output is correct
2 Correct 7 ms 1748 KB Output is correct
3 Correct 7 ms 1748 KB Output is correct
4 Correct 8 ms 1748 KB Output is correct
5 Correct 7 ms 1736 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 9 ms 1788 KB Output is correct
8 Correct 641 ms 85416 KB Output is correct
9 Correct 53 ms 2508 KB Output is correct
10 Correct 515 ms 93560 KB Output is correct
11 Correct 678 ms 93648 KB Output is correct
12 Correct 554 ms 93696 KB Output is correct
13 Correct 663 ms 93692 KB Output is correct
14 Correct 614 ms 90560 KB Output is correct
15 Correct 666 ms 93576 KB Output is correct
16 Correct 576 ms 93660 KB Output is correct
17 Correct 438 ms 93760 KB Output is correct
18 Correct 552 ms 93704 KB Output is correct
19 Correct 625 ms 93760 KB Output is correct
20 Correct 345 ms 93668 KB Output is correct
21 Correct 341 ms 93628 KB Output is correct
22 Correct 209 ms 23440 KB Output is correct
23 Correct 209 ms 23440 KB Output is correct
24 Correct 264 ms 24440 KB Output is correct
25 Correct 142 ms 24120 KB Output is correct
26 Correct 232 ms 24556 KB Output is correct
27 Correct 235 ms 24516 KB Output is correct
28 Correct 195 ms 24488 KB Output is correct
29 Correct 242 ms 23468 KB Output is correct
30 Correct 219 ms 24540 KB Output is correct
31 Correct 203 ms 24548 KB Output is correct
32 Correct 98 ms 24524 KB Output is correct
33 Correct 98 ms 24352 KB Output is correct
34 Correct 1 ms 320 KB Output is correct
35 Correct 1 ms 328 KB Output is correct
36 Correct 817 ms 90852 KB Output is correct
37 Correct 835 ms 93808 KB Output is correct
38 Correct 509 ms 92848 KB Output is correct
39 Correct 820 ms 94040 KB Output is correct
40 Correct 896 ms 90860 KB Output is correct
41 Correct 725 ms 93832 KB Output is correct
42 Correct 718 ms 90956 KB Output is correct
43 Correct 859 ms 93900 KB Output is correct
44 Correct 838 ms 93860 KB Output is correct
45 Correct 834 ms 93852 KB Output is correct
46 Correct 738 ms 93964 KB Output is correct
47 Correct 587 ms 94100 KB Output is correct