oj.uz

Submission #635397

# Submission time Handle Problem Language Result Execution time Memory
635397 2022-08-26T08:20:04 Z NothingXD ZIGZAG (INOI20_zigzag) C++17
100 / 100
 928 ms 63164 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << H;
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

const int maxn = 3e5 + 10;

struct Seg{
	ll ans, x, y;
	int l, r, sz;
	Seg(){};
	Seg(ll x, ll y, int l, int r, int sz, ll ans){
		this->l = l;
		this->r = r;
		this->x = x;
		this->y = y;
		this->sz = sz;
		this->ans = ans;
	}
};

Seg operator +(Seg a, Seg b){
	Seg res;
	if (a.sz == 0) return b;
	if (b.sz == 0) return a;
	res.ans = a.ans + b.ans;
	res.sz = a.sz + b.sz;
	res.x = a.x;
	res.y = b.y;
	res.l = a.l;
	res.r = b.r;
	if (a.y > b.x){
		res.ans += 1ll * (max(0, -a.r) + 1) * (max(0, b.l) + 1);
		if (a.l == 0 && a.sz == 1){
			res.l = -max(b.l, 0) - 1;
		}
		else if (abs(a.l) == -a.r && abs(a.l) == a.sz - 1){
			if (a.l < 0) res.l = a.l - max(0, b.l) - 1;
			else res.l = a.l + max(0, b.l) + 1;
		}
		if (b.r == 0 && b.sz == 1){
			res.r = max(-a.r, 0) + 1;
		}
		else if (b.l == abs(b.r) && abs(b.r) == b.sz - 1){
			if (b.r < 0) res.r = b.r - max(0, -a.r) - 1;
			else res.r = b.r + max(0, -a.r) + 1;
		}
	}
	else if (a.y < b.x){
		res.ans += 1ll * (max(0, a.r) + 1) * (max(0, -b.l) + 1);
		if (a.l == 0 && a.sz == 1){
			res.l = max(-b.l, 0) + 1;
		}
		else if (abs(a.l) == a.r && abs(a.l) == a.sz - 1){
			if (a.l < 0) res.l = a.l - max(0, -b.l) - 1;
			else res.l = a.l + max(0, -b.l) + 1;
		}
		if (b.r == 0 && b.sz == 1){
			res.r = -max(a.r, 0) - 1;
		}
		else if (-b.l == abs(b.r) && abs(b.r) == b.sz - 1){
			if (b.r < 0) res.r = b.r - max(0, a.r) - 1;
			else res.r = b.r + max(0, a.r) + 1;
		}
	}
	return res;
}

int n, q, a[maxn];
pll lazy[maxn << 2];
Seg seg[maxn << 2];

void build(int v, int l, int r){
	if (l + 1 == r){
		seg[v] = Seg(a[l], a[l], 0, 0, 1, 1);
		return;
	}
	int mid = (l + r) >> 1;
	build(v << 1, l, mid);
	build(v << 1 | 1, mid, r);
	seg[v] = seg[v << 1] + seg[v << 1 | 1];
//	debug(l, r, seg[v].x, seg[v].y, seg[v].l, seg[v].r, seg[v].sz, seg[v].ans);
}

void shift(int v, int l, int r);

void add(int v, int l, int r, int ql, int qr, ll val){
	if (qr <= l || r <= ql) return;
	if (ql <= l && r <= qr){
		seg[v].x += val;
		seg[v].y += val;
		lazy[v].F += val;
		return;
	}
	shift(v, l, r);
	int mid = (l + r) >> 1;
	add(v << 1, l, mid, ql, qr, val);
	add(v << 1 | 1, mid, r, ql, qr, val);
	seg[v] = seg[v << 1] + seg[v << 1 | 1];
}

void reverse(int v, int l, int r, int ql, int qr){
	if (qr <= l || r <= ql) return;
	if (ql <= l && r <= qr){
		seg[v].x = -seg[v].x;
		seg[v].y = -seg[v].y;
		seg[v].l = -seg[v].l;
		seg[v].r = -seg[v].r;
		lazy[v].S++;
		lazy[v].F = -lazy[v].F;
		return;
	}
	shift(v, l, r);
	int mid = (l + r) >> 1;
	reverse(v << 1, l, mid, ql, qr);
	reverse(v << 1 | 1, mid, r, ql, qr);
	seg[v] = seg[v << 1] + seg[v << 1 | 1];
}

Seg get(int v, int l, int r, int ql, int qr){
	if (qr <= l || r <= ql) return Seg(0, 0, 0, 0, 0, 0);
	if (ql <= l && r <= qr) return seg[v];
	shift(v, l, r);
	int mid = (l + r) >> 1;
	return get(v << 1, l, mid, ql, qr)
		+ get(v << 1 | 1, mid, r, ql, qr);
}

void shift(int v, int l, int r){
	if (lazy[v].S & 1){
		int mid = (l + r) >> 1;
		reverse(v << 1, l, mid, l, mid);
		reverse(v << 1 | 1, mid, r, mid, r);
		lazy[v].S = 0;
	}
	if (lazy[v].F == 0) return;
	int mid = (l + r) >> 1;
	add(v << 1, l, mid, l, mid, lazy[v].F);
	add(v << 1 | 1, mid, r, mid, r, lazy[v].F);
	lazy[v].F = 0;
}

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

	cin >> n >> q;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
	}

	build(1, 1, n+1);

	while(q--){
		char t; int l, r; cin >> t >> l >> r;
		if (t == '*') reverse(1, 1, n+1, l, r+1);
		else if (t == '+'){
			int x; cin >> x;
			add(1, 1, n+1, l, r+1, x);
		}
		else{
			cout << get(1, 1, n+1, l, r+1).ans << '\n';
		}
	}

	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1316 KB Output is correct
2 Correct 7 ms 1236 KB Output is correct
3 Correct 9 ms 1236 KB Output is correct
4 Correct 8 ms 1236 KB Output is correct
5 Correct 7 ms 1268 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 6 ms 1036 KB Output is correct

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 661 ms 59536 KB Output is correct
2 Correct 51 ms 468 KB Output is correct
3 Correct 467 ms 59700 KB Output is correct
4 Correct 646 ms 62848 KB Output is correct
5 Correct 575 ms 62808 KB Output is correct
6 Correct 706 ms 62848 KB Output is correct
7 Correct 659 ms 62828 KB Output is correct
8 Correct 669 ms 62884 KB Output is correct
9 Correct 589 ms 62888 KB Output is correct
10 Correct 420 ms 61288 KB Output is correct
11 Correct 582 ms 62876 KB Output is correct
12 Correct 674 ms 63164 KB Output is correct
13 Correct 244 ms 59712 KB Output is correct
14 Correct 307 ms 59588 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1316 KB Output is correct
2 Correct 7 ms 1236 KB Output is correct
3 Correct 9 ms 1236 KB Output is correct
4 Correct 8 ms 1236 KB Output is correct
5 Correct 7 ms 1268 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 6 ms 1036 KB Output is correct
8 Correct 232 ms 16320 KB Output is correct
9 Correct 258 ms 17000 KB Output is correct
10 Correct 262 ms 17904 KB Output is correct
11 Correct 136 ms 13604 KB Output is correct
12 Correct 274 ms 17996 KB Output is correct
13 Correct 270 ms 17980 KB Output is correct
14 Correct 206 ms 17980 KB Output is correct
15 Correct 229 ms 16968 KB Output is correct
16 Correct 254 ms 17996 KB Output is correct
17 Correct 202 ms 17904 KB Output is correct
18 Correct 73 ms 16952 KB Output is correct
19 Correct 84 ms 16880 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1316 KB Output is correct
2 Correct 7 ms 1236 KB Output is correct
3 Correct 9 ms 1236 KB Output is correct
4 Correct 8 ms 1236 KB Output is correct
5 Correct 7 ms 1268 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 6 ms 1036 KB Output is correct
8 Correct 661 ms 59536 KB Output is correct
9 Correct 51 ms 468 KB Output is correct
10 Correct 467 ms 59700 KB Output is correct
11 Correct 646 ms 62848 KB Output is correct
12 Correct 575 ms 62808 KB Output is correct
13 Correct 706 ms 62848 KB Output is correct
14 Correct 659 ms 62828 KB Output is correct
15 Correct 669 ms 62884 KB Output is correct
16 Correct 589 ms 62888 KB Output is correct
17 Correct 420 ms 61288 KB Output is correct
18 Correct 582 ms 62876 KB Output is correct
19 Correct 674 ms 63164 KB Output is correct
20 Correct 244 ms 59712 KB Output is correct
21 Correct 307 ms 59588 KB Output is correct
22 Correct 232 ms 16320 KB Output is correct
23 Correct 258 ms 17000 KB Output is correct
24 Correct 262 ms 17904 KB Output is correct
25 Correct 136 ms 13604 KB Output is correct
26 Correct 274 ms 17996 KB Output is correct
27 Correct 270 ms 17980 KB Output is correct
28 Correct 206 ms 17980 KB Output is correct
29 Correct 229 ms 16968 KB Output is correct
30 Correct 254 ms 17996 KB Output is correct
31 Correct 202 ms 17904 KB Output is correct
32 Correct 73 ms 16952 KB Output is correct
33 Correct 84 ms 16880 KB Output is correct
34 Correct 0 ms 340 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 872 ms 62776 KB Output is correct
37 Correct 876 ms 62684 KB Output is correct
38 Correct 439 ms 46620 KB Output is correct
39 Correct 928 ms 62948 KB Output is correct
40 Correct 842 ms 62788 KB Output is correct
41 Correct 772 ms 62804 KB Output is correct
42 Correct 752 ms 62948 KB Output is correct
43 Correct 847 ms 62764 KB Output is correct
44 Correct 881 ms 62752 KB Output is correct
45 Correct 891 ms 62804 KB Output is correct
46 Correct 804 ms 62924 KB Output is correct
47 Correct 465 ms 59416 KB Output is correct