oj.uz

Submission #585188

# Submission time Handle Problem Language Result Execution time Memory
585188 2022-06-28T12:11:13 Z GioChkhaidze Progression (NOI20_progression) C++14
57 / 100
 868 ms 72140 KB 
// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>

#define lf (h << 1)
#define mf ((l + r) >> 1)
#define rf ((h << 1) | 1)
#define tree int h, int l, int r 
#define left lf, l, mf
#define right rf, mf + 1, r
#define ll long long
#define f first
#define s second

using namespace std;

const int N = 3e5 + 5;

int n, m, q, L, R, id;
ll S, C, vl, a[N], b[N];

struct node {
	int ans;
	int len;
	int fr;
	int ls;
	int pr;
	int sf;
	ll add;
	ll sum;
	ll toggle;
	bool flag;
	node () {
		toggle = 0;
		flag = 0;
		sum = 0;
		ans = 0;
		len = 0;
		add = 0;
		fr = 0;
		ls = 0;
		pr = 0;
		sf = 0;
	}
};

node v[4 * N], bs;

node mrg(node a, node b) {
	node c;
	c.len = a.len + b.len;
	c.fr = a.fr, c.ls = b.ls;
	c.pr = a.pr, c.sf = b.sf;
	c.ans = max(a.ans, b.ans);
	c.sum = a.sum + b.sum;
	if (a.ls == b.fr) {
		if (a.len == c.pr) c.pr += b.pr;
		if (b.len == c.sf) c.sf += a.sf;
		c.ans = max(c.ans, a.sf + b.pr);
	}
	return c;
} 

void shift(tree) {
	if (v[h].flag) {
		assert(v[h].add == 0);
		ll x = v[h].toggle;
		v[lf].fr = v[lf].ls = v[rf].fr = v[rf].ls =x;
		v[lf].ans = v[lf].pr = v[lf].sf = mf - l + 1;
		v[rf].ans = v[rf].pr = v[rf].sf = r - mf;
		v[lf].toggle = v[rf].toggle = x;
		v[lf].flag = v[rf].flag = true;
		v[lf].add = v[rf].add = false; 
		v[lf].sum = (mf - l + 1) * x;
		v[rf].sum = (r - mf) * x;
		v[h].toggle = 0;
		v[h].flag = 0;
		return ;
	}

	if (v[h].add) {
		v[lf].fr += v[h].add;
		v[lf].ls += v[h].add;
		v[rf].fr += v[h].add;
		v[rf].ls += v[h].add;
		v[lf].sum += (mf - l + 1) * v[h].add;
		v[rf].sum += (r - mf) * v[h].add;

		if (v[lf].flag) v[lf].toggle += v[h].add;
			else v[lf].add += v[h].add;
		
		if (v[rf].flag) v[rf].toggle += v[h].add;
			else v[rf].add += v[h].add;

		v[h].add = 0;
		return ;
	}
}

void build(tree) {
	if (l == r) {
		v[h].pr = v[h].sf = v[h].len = v[h].ans = 1;
		v[h].fr = v[h].ls = v[h].sum = b[l];
		return ;
	}
	build(left), build(right);
	v[h] = mrg(v[lf], v[rf]);
}

void up_range(tree) {
	if (R < l || r < L) return ;
	if (L <= l && r <= R) {
		v[h].fr += C, v[h].ls += C;
		v[h].sum += (r - l + 1) * C;
		if (v[h].flag) {
			v[h].toggle += C;
			v[h].add = 0;
		}
			else {
			v[h].add += C;
		}
		return;
	}
	shift(h, l, r);
	up_range(left);
	up_range(right);
	v[h] = mrg(v[lf], v[rf]);
}

void up_dot(tree) {
	if (l == r) {
		v[h].pr = v[h].sf = v[h].len = v[h].ans = 1;
		v[h].fr = v[h].ls = v[h].sum = b[l];
		return;
	}
	shift(h, l, r);
	if (id <= mf) {
		up_dot(left);
	}
		else {
		up_dot(right);
	}
	v[h] = mrg(v[lf], v[rf]);
}

void up_to_range(tree) {
	if (r < L || R < l) return ;
	if (L <= l && r <= R) {
		v[h].ans = v[h].pr = v[h].sf = r - l + 1;
		v[h].toggle = v[h].fr = v[h].ls = C;
		v[h].sum = (r - l + 1) * C;
		v[h].flag = true;
		v[h].add = 0;
		return;
	}
	shift(h, l, r);
	up_to_range(left);
	up_to_range(right);
	v[h] = mrg(v[lf], v[rf]);
}

ll get_avl(tree, int id) {
	if (r < 1 || id < l) return 0;
	if (1 <= l && r <= id) return v[h].sum;
	shift(h, l, r);
	return get_avl(left, id) + get_avl(right, id);
}

ll get_vl(tree) {
	if (l == r) return v[h].fr;
	shift(h, l, r);
	if (id <= mf) {
		ll x =  get_vl(left);
		v[h] = mrg(v[lf], v[rf]);
		return x;
	}
	ll x = get_vl(right);
	v[h] = mrg(v[lf], v[rf]);
	return x;
}

node get(tree) {
	if (r < L || R < l) return bs;
	if (L <= l && r <= R) return v[h];
	shift(h, l, r);
	return mrg(get(left), get(right));
}

ll Avl(int x) {
	return a[1] + get_avl(1, 1, m, x - 1);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> q;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		if (1 < i) {
			b[i - 1] = a[i] - a[i - 1];
		} 
	}

	m = n + 1;
	build(1, 1, m);
	for (int i = 1; i <= q; ++i) {
		int tp;
		cin >> tp >> L >> R;
		if (tp == 1) {
			cin >> S >> C;
			if (L == 1) a[1] += S;
			--R, up_range(1, 1, m), ++R;
			if (1 < L) {
				id = L - 1;
				vl = get_vl(1, 1, m);
				b[id] = vl + S;
				up_dot(1, 1, m);
			}

			if (R < n) {
				id = R;
				vl = get_vl(1 , 1, m);
				b[id] = vl - (S + (R - L) * C); 
				up_dot(1, 1, m);
			}
		}
			else
		if (tp == 2) {
			cin >> S >> C;
			if (L == 1) a[1] = S;

			if (R < n) {
				id = R;
				b[id] = Avl(id + 1) - (S + (R - L) * C); 
				up_dot(1, 1, m);
			}

			--R, up_to_range(1, 1, m), ++R;

			if (1 < L) {
				id = L - 1;
				b[id] = S - Avl(id); 
				up_dot(1, 1, m);
			}
		}
			else
		if (tp == 3) {
			--R; cout << get(1 , 1, m).ans + 1 << "\n";
		}
	}
}

/*
 S + (i − L) × C.

 S + i * C - L * C

 (S - L * C) + i * C

b[i] = a[i + 1] - a[i]
*/

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 71288 KB Output is correct
2 Correct 131 ms 66356 KB Output is correct
3 Correct 140 ms 66372 KB Output is correct
4 Correct 136 ms 66376 KB Output is correct
5 Correct 169 ms 66424 KB Output is correct
6 Correct 134 ms 66380 KB Output is correct
7 Correct 170 ms 66368 KB Output is correct
8 Correct 34 ms 66052 KB Output is correct
9 Correct 35 ms 66004 KB Output is correct
10 Correct 31 ms 65972 KB Output is correct
11 Correct 245 ms 71300 KB Output is correct
12 Correct 249 ms 71312 KB Output is correct
13 Correct 257 ms 71544 KB Output is correct
14 Correct 247 ms 71624 KB Output is correct
15 Correct 279 ms 71524 KB Output is correct
16 Correct 278 ms 71312 KB Output is correct
17 Correct 257 ms 71264 KB Output is correct
18 Correct 276 ms 71312 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 66072 KB Output is correct
2 Correct 29 ms 66004 KB Output is correct
3 Correct 30 ms 66004 KB Output is correct
4 Correct 27 ms 66004 KB Output is correct
5 Correct 31 ms 66072 KB Output is correct
6 Correct 29 ms 66088 KB Output is correct
7 Correct 31 ms 66088 KB Output is correct
8 Correct 30 ms 66040 KB Output is correct
9 Correct 30 ms 65996 KB Output is correct
10 Correct 33 ms 66072 KB Output is correct
11 Correct 37 ms 66072 KB Output is correct
12 Correct 40 ms 66068 KB Output is correct
13 Correct 30 ms 66096 KB Output is correct
14 Correct 31 ms 66004 KB Output is correct
15 Correct 30 ms 66088 KB Output is correct
16 Correct 30 ms 66072 KB Output is correct
17 Correct 30 ms 66016 KB Output is correct
18 Correct 30 ms 65996 KB Output is correct
19 Correct 38 ms 66036 KB Output is correct
20 Incorrect 31 ms 66004 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 71864 KB Output is correct
2 Correct 140 ms 66604 KB Output is correct
3 Correct 127 ms 66668 KB Output is correct
4 Correct 115 ms 66572 KB Output is correct
5 Correct 136 ms 66700 KB Output is correct
6 Correct 139 ms 66632 KB Output is correct
7 Correct 128 ms 66632 KB Output is correct
8 Correct 32 ms 65968 KB Output is correct
9 Correct 30 ms 66064 KB Output is correct
10 Correct 29 ms 66004 KB Output is correct
11 Correct 365 ms 71584 KB Output is correct
12 Correct 349 ms 71844 KB Output is correct
13 Correct 321 ms 71528 KB Output is correct
14 Correct 349 ms 71560 KB Output is correct
15 Correct 291 ms 71752 KB Output is correct
16 Correct 563 ms 72100 KB Output is correct
17 Correct 338 ms 72140 KB Output is correct
18 Correct 395 ms 72136 KB Output is correct
19 Correct 307 ms 71376 KB Output is correct
20 Correct 295 ms 71460 KB Output is correct
21 Correct 292 ms 71372 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 796 ms 71004 KB Output is correct
2 Incorrect 180 ms 66288 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 71864 KB Output is correct
2 Correct 140 ms 66604 KB Output is correct
3 Correct 127 ms 66668 KB Output is correct
4 Correct 115 ms 66572 KB Output is correct
5 Correct 136 ms 66700 KB Output is correct
6 Correct 139 ms 66632 KB Output is correct
7 Correct 128 ms 66632 KB Output is correct
8 Correct 32 ms 65968 KB Output is correct
9 Correct 30 ms 66064 KB Output is correct
10 Correct 29 ms 66004 KB Output is correct
11 Correct 365 ms 71584 KB Output is correct
12 Correct 349 ms 71844 KB Output is correct
13 Correct 321 ms 71528 KB Output is correct
14 Correct 349 ms 71560 KB Output is correct
15 Correct 291 ms 71752 KB Output is correct
16 Correct 563 ms 72100 KB Output is correct
17 Correct 338 ms 72140 KB Output is correct
18 Correct 395 ms 72136 KB Output is correct
19 Correct 307 ms 71376 KB Output is correct
20 Correct 295 ms 71460 KB Output is correct
21 Correct 292 ms 71372 KB Output is correct
22 Correct 825 ms 71144 KB Output is correct
23 Correct 180 ms 66348 KB Output is correct
24 Correct 190 ms 66360 KB Output is correct
25 Correct 223 ms 66472 KB Output is correct
26 Correct 191 ms 66340 KB Output is correct
27 Correct 189 ms 66456 KB Output is correct
28 Correct 192 ms 66396 KB Output is correct
29 Correct 29 ms 66032 KB Output is correct
30 Correct 31 ms 65996 KB Output is correct
31 Correct 30 ms 66004 KB Output is correct
32 Correct 867 ms 71180 KB Output is correct
33 Correct 800 ms 71112 KB Output is correct
34 Correct 808 ms 71064 KB Output is correct
35 Correct 799 ms 71124 KB Output is correct
36 Correct 621 ms 71292 KB Output is correct
37 Correct 652 ms 71344 KB Output is correct
38 Correct 617 ms 71388 KB Output is correct
39 Correct 786 ms 71076 KB Output is correct
40 Correct 868 ms 71180 KB Output is correct
41 Correct 839 ms 71184 KB Output is correct
42 Correct 845 ms 71352 KB Output is correct
43 Correct 826 ms 71200 KB Output is correct
44 Correct 799 ms 71084 KB Output is correct
45 Correct 772 ms 71180 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 276 ms 71288 KB Output is correct
2 Correct 131 ms 66356 KB Output is correct
3 Correct 140 ms 66372 KB Output is correct
4 Correct 136 ms 66376 KB Output is correct
5 Correct 169 ms 66424 KB Output is correct
6 Correct 134 ms 66380 KB Output is correct
7 Correct 170 ms 66368 KB Output is correct
8 Correct 34 ms 66052 KB Output is correct
9 Correct 35 ms 66004 KB Output is correct
10 Correct 31 ms 65972 KB Output is correct
11 Correct 245 ms 71300 KB Output is correct
12 Correct 249 ms 71312 KB Output is correct
13 Correct 257 ms 71544 KB Output is correct
14 Correct 247 ms 71624 KB Output is correct
15 Correct 279 ms 71524 KB Output is correct
16 Correct 278 ms 71312 KB Output is correct
17 Correct 257 ms 71264 KB Output is correct
18 Correct 276 ms 71312 KB Output is correct
19 Correct 34 ms 66072 KB Output is correct
20 Correct 29 ms 66004 KB Output is correct
21 Correct 30 ms 66004 KB Output is correct
22 Correct 27 ms 66004 KB Output is correct
23 Correct 31 ms 66072 KB Output is correct
24 Correct 29 ms 66088 KB Output is correct
25 Correct 31 ms 66088 KB Output is correct
26 Correct 30 ms 66040 KB Output is correct
27 Correct 30 ms 65996 KB Output is correct
28 Correct 33 ms 66072 KB Output is correct
29 Correct 37 ms 66072 KB Output is correct
30 Correct 40 ms 66068 KB Output is correct
31 Correct 30 ms 66096 KB Output is correct
32 Correct 31 ms 66004 KB Output is correct
33 Correct 30 ms 66088 KB Output is correct
34 Correct 30 ms 66072 KB Output is correct
35 Correct 30 ms 66016 KB Output is correct
36 Correct 30 ms 65996 KB Output is correct
37 Correct 38 ms 66036 KB Output is correct
38 Incorrect 31 ms 66004 KB Output isn't correct
39 Halted 0 ms 0 KB -