oj.uz

Submission #585196

# Submission time Handle Problem Language Result Execution time Memory
585196 2022-06-28T12:19:50 Z GioChkhaidze Progression (NOI20_progression) C++14
57 / 100
 777 ms 72176 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].sum = (mf - l + 1) * x, v[rf].sum = (r - mf) * x;
		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[h].toggle =v[h].flag = 0;
		return ;
	}

	if (v[h].add) {
		ll x = v[h].add;
		assert(v[h].flag == 0);
		assert(v[h].toggle == 0);
		v[lf].fr += x, v[lf].ls += x;
		v[rf].fr += x, v[rf].ls += x;
		v[lf].sum += (mf - l + 1) * x, v[rf].sum += (r - mf) * x;

		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;
			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) {
		return get_vl(left);
	}
	return get_vl(right);
}

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 288 ms 71484 KB Output is correct
2 Correct 124 ms 66308 KB Output is correct
3 Correct 123 ms 66368 KB Output is correct
4 Correct 142 ms 66312 KB Output is correct
5 Correct 125 ms 66448 KB Output is correct
6 Correct 124 ms 66432 KB Output is correct
7 Correct 123 ms 66300 KB Output is correct
8 Correct 27 ms 66012 KB Output is correct
9 Correct 28 ms 66004 KB Output is correct
10 Correct 28 ms 66076 KB Output is correct
11 Correct 242 ms 71500 KB Output is correct
12 Correct 238 ms 71372 KB Output is correct
13 Correct 242 ms 71724 KB Output is correct
14 Correct 250 ms 71716 KB Output is correct
15 Correct 239 ms 71752 KB Output is correct
16 Correct 244 ms 71456 KB Output is correct
17 Correct 245 ms 71432 KB Output is correct
18 Correct 237 ms 71344 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 65996 KB Output is correct
2 Correct 31 ms 66036 KB Output is correct
3 Correct 28 ms 66036 KB Output is correct
4 Correct 29 ms 66032 KB Output is correct
5 Correct 28 ms 65976 KB Output is correct
6 Correct 33 ms 66024 KB Output is correct
7 Correct 35 ms 66000 KB Output is correct
8 Correct 29 ms 65980 KB Output is correct
9 Correct 29 ms 66032 KB Output is correct
10 Correct 29 ms 66052 KB Output is correct
11 Correct 29 ms 65996 KB Output is correct
12 Correct 30 ms 66000 KB Output is correct
13 Correct 29 ms 66004 KB Output is correct
14 Correct 28 ms 66004 KB Output is correct
15 Correct 29 ms 65996 KB Output is correct
16 Correct 29 ms 66024 KB Output is correct
17 Correct 30 ms 66048 KB Output is correct
18 Correct 36 ms 66044 KB Output is correct
19 Correct 30 ms 65992 KB Output is correct
20 Incorrect 28 ms 66076 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 291 ms 71752 KB Output is correct
2 Correct 125 ms 66656 KB Output is correct
3 Correct 124 ms 66644 KB Output is correct
4 Correct 107 ms 66576 KB Output is correct
5 Correct 117 ms 66708 KB Output is correct
6 Correct 126 ms 66656 KB Output is correct
7 Correct 119 ms 66772 KB Output is correct
8 Correct 29 ms 66064 KB Output is correct
9 Correct 30 ms 65960 KB Output is correct
10 Correct 30 ms 66032 KB Output is correct
11 Correct 312 ms 71488 KB Output is correct
12 Correct 293 ms 71800 KB Output is correct
13 Correct 330 ms 71488 KB Output is correct
14 Correct 298 ms 71600 KB Output is correct
15 Correct 295 ms 71840 KB Output is correct
16 Correct 309 ms 72060 KB Output is correct
17 Correct 347 ms 72084 KB Output is correct
18 Correct 330 ms 72176 KB Output is correct
19 Correct 290 ms 71408 KB Output is correct
20 Correct 290 ms 71484 KB Output is correct
21 Correct 287 ms 71380 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 649 ms 70988 KB Output is correct
2 Incorrect 179 ms 66200 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 291 ms 71752 KB Output is correct
2 Correct 125 ms 66656 KB Output is correct
3 Correct 124 ms 66644 KB Output is correct
4 Correct 107 ms 66576 KB Output is correct
5 Correct 117 ms 66708 KB Output is correct
6 Correct 126 ms 66656 KB Output is correct
7 Correct 119 ms 66772 KB Output is correct
8 Correct 29 ms 66064 KB Output is correct
9 Correct 30 ms 65960 KB Output is correct
10 Correct 30 ms 66032 KB Output is correct
11 Correct 312 ms 71488 KB Output is correct
12 Correct 293 ms 71800 KB Output is correct
13 Correct 330 ms 71488 KB Output is correct
14 Correct 298 ms 71600 KB Output is correct
15 Correct 295 ms 71840 KB Output is correct
16 Correct 309 ms 72060 KB Output is correct
17 Correct 347 ms 72084 KB Output is correct
18 Correct 330 ms 72176 KB Output is correct
19 Correct 290 ms 71408 KB Output is correct
20 Correct 290 ms 71484 KB Output is correct
21 Correct 287 ms 71380 KB Output is correct
22 Correct 729 ms 71308 KB Output is correct
23 Correct 167 ms 66380 KB Output is correct
24 Correct 165 ms 66340 KB Output is correct
25 Correct 174 ms 66352 KB Output is correct
26 Correct 175 ms 66520 KB Output is correct
27 Correct 163 ms 66356 KB Output is correct
28 Correct 171 ms 66272 KB Output is correct
29 Correct 30 ms 66052 KB Output is correct
30 Correct 31 ms 65976 KB Output is correct
31 Correct 35 ms 66048 KB Output is correct
32 Correct 735 ms 71308 KB Output is correct
33 Correct 684 ms 71112 KB Output is correct
34 Correct 738 ms 71244 KB Output is correct
35 Correct 734 ms 71272 KB Output is correct
36 Correct 563 ms 71500 KB Output is correct
37 Correct 561 ms 71500 KB Output is correct
38 Correct 571 ms 71476 KB Output is correct
39 Correct 718 ms 71112 KB Output is correct
40 Correct 777 ms 71152 KB Output is correct
41 Correct 739 ms 71324 KB Output is correct
42 Correct 740 ms 71328 KB Output is correct
43 Correct 688 ms 71084 KB Output is correct
44 Correct 729 ms 71128 KB Output is correct
45 Correct 706 ms 71144 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 71484 KB Output is correct
2 Correct 124 ms 66308 KB Output is correct
3 Correct 123 ms 66368 KB Output is correct
4 Correct 142 ms 66312 KB Output is correct
5 Correct 125 ms 66448 KB Output is correct
6 Correct 124 ms 66432 KB Output is correct
7 Correct 123 ms 66300 KB Output is correct
8 Correct 27 ms 66012 KB Output is correct
9 Correct 28 ms 66004 KB Output is correct
10 Correct 28 ms 66076 KB Output is correct
11 Correct 242 ms 71500 KB Output is correct
12 Correct 238 ms 71372 KB Output is correct
13 Correct 242 ms 71724 KB Output is correct
14 Correct 250 ms 71716 KB Output is correct
15 Correct 239 ms 71752 KB Output is correct
16 Correct 244 ms 71456 KB Output is correct
17 Correct 245 ms 71432 KB Output is correct
18 Correct 237 ms 71344 KB Output is correct
19 Correct 33 ms 65996 KB Output is correct
20 Correct 31 ms 66036 KB Output is correct
21 Correct 28 ms 66036 KB Output is correct
22 Correct 29 ms 66032 KB Output is correct
23 Correct 28 ms 65976 KB Output is correct
24 Correct 33 ms 66024 KB Output is correct
25 Correct 35 ms 66000 KB Output is correct
26 Correct 29 ms 65980 KB Output is correct
27 Correct 29 ms 66032 KB Output is correct
28 Correct 29 ms 66052 KB Output is correct
29 Correct 29 ms 65996 KB Output is correct
30 Correct 30 ms 66000 KB Output is correct
31 Correct 29 ms 66004 KB Output is correct
32 Correct 28 ms 66004 KB Output is correct
33 Correct 29 ms 65996 KB Output is correct
34 Correct 29 ms 66024 KB Output is correct
35 Correct 30 ms 66048 KB Output is correct
36 Correct 36 ms 66044 KB Output is correct
37 Correct 30 ms 65992 KB Output is correct
38 Incorrect 28 ms 66076 KB Output isn't correct
39 Halted 0 ms 0 KB -