oj.uz

Submission #585185

# Submission time Handle Problem Language Result Execution time Memory
585185 2022-06-28T12:08:41 Z GioChkhaidze Progression (NOI20_progression) C++14
57 / 100
 824 ms 77196 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 = x;
		v[rf].fr = v[rf].ls =x;
		v[h].ans = v[h].pr = v[h].sf = r - l + 1;
		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 238 ms 72376 KB Output is correct
2 Correct 123 ms 69204 KB Output is correct
3 Correct 125 ms 69280 KB Output is correct
4 Correct 137 ms 69292 KB Output is correct
5 Correct 127 ms 69356 KB Output is correct
6 Correct 125 ms 69276 KB Output is correct
7 Correct 123 ms 69288 KB Output is correct
8 Correct 32 ms 66076 KB Output is correct
9 Correct 33 ms 66088 KB Output is correct
10 Correct 28 ms 66000 KB Output is correct
11 Correct 239 ms 76888 KB Output is correct
12 Correct 258 ms 76908 KB Output is correct
13 Correct 242 ms 77112 KB Output is correct
14 Correct 245 ms 77196 KB Output is correct
15 Correct 241 ms 77152 KB Output is correct
16 Correct 246 ms 76760 KB Output is correct
17 Correct 237 ms 76812 KB Output is correct
18 Correct 240 ms 76812 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 66048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 72760 KB Output is correct
2 Correct 120 ms 67568 KB Output is correct
3 Correct 120 ms 67528 KB Output is correct
4 Correct 116 ms 67492 KB Output is correct
5 Correct 118 ms 67536 KB Output is correct
6 Correct 138 ms 67580 KB Output is correct
7 Correct 128 ms 67656 KB Output is correct
8 Correct 33 ms 65980 KB Output is correct
9 Correct 29 ms 66000 KB Output is correct
10 Correct 28 ms 66028 KB Output is correct
11 Correct 341 ms 72528 KB Output is correct
12 Correct 304 ms 72852 KB Output is correct
13 Correct 343 ms 72304 KB Output is correct
14 Correct 320 ms 72292 KB Output is correct
15 Correct 303 ms 72464 KB Output is correct
16 Correct 318 ms 72936 KB Output is correct
17 Correct 330 ms 72884 KB Output is correct
18 Correct 309 ms 73052 KB Output is correct
19 Correct 299 ms 72136 KB Output is correct
20 Correct 285 ms 72220 KB Output is correct
21 Correct 302 ms 72292 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 663 ms 71732 KB Output is correct
2 Incorrect 178 ms 68152 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 309 ms 72760 KB Output is correct
2 Correct 120 ms 67568 KB Output is correct
3 Correct 120 ms 67528 KB Output is correct
4 Correct 116 ms 67492 KB Output is correct
5 Correct 118 ms 67536 KB Output is correct
6 Correct 138 ms 67580 KB Output is correct
7 Correct 128 ms 67656 KB Output is correct
8 Correct 33 ms 65980 KB Output is correct
9 Correct 29 ms 66000 KB Output is correct
10 Correct 28 ms 66028 KB Output is correct
11 Correct 341 ms 72528 KB Output is correct
12 Correct 304 ms 72852 KB Output is correct
13 Correct 343 ms 72304 KB Output is correct
14 Correct 320 ms 72292 KB Output is correct
15 Correct 303 ms 72464 KB Output is correct
16 Correct 318 ms 72936 KB Output is correct
17 Correct 330 ms 72884 KB Output is correct
18 Correct 309 ms 73052 KB Output is correct
19 Correct 299 ms 72136 KB Output is correct
20 Correct 285 ms 72220 KB Output is correct
21 Correct 302 ms 72292 KB Output is correct
22 Correct 794 ms 71964 KB Output is correct
23 Correct 197 ms 67396 KB Output is correct
24 Correct 179 ms 67384 KB Output is correct
25 Correct 182 ms 67312 KB Output is correct
26 Correct 177 ms 67472 KB Output is correct
27 Correct 184 ms 67492 KB Output is correct
28 Correct 180 ms 67316 KB Output is correct
29 Correct 30 ms 66100 KB Output is correct
30 Correct 32 ms 65996 KB Output is correct
31 Correct 30 ms 66032 KB Output is correct
32 Correct 789 ms 72652 KB Output is correct
33 Correct 765 ms 72716 KB Output is correct
34 Correct 779 ms 72684 KB Output is correct
35 Correct 770 ms 72776 KB Output is correct
36 Correct 628 ms 72940 KB Output is correct
37 Correct 649 ms 72884 KB Output is correct
38 Correct 677 ms 73084 KB Output is correct
39 Correct 787 ms 72700 KB Output is correct
40 Correct 804 ms 72900 KB Output is correct
41 Correct 798 ms 72760 KB Output is correct
42 Correct 824 ms 72872 KB Output is correct
43 Correct 761 ms 72676 KB Output is correct
44 Correct 803 ms 72468 KB Output is correct
45 Correct 775 ms 72416 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 72376 KB Output is correct
2 Correct 123 ms 69204 KB Output is correct
3 Correct 125 ms 69280 KB Output is correct
4 Correct 137 ms 69292 KB Output is correct
5 Correct 127 ms 69356 KB Output is correct
6 Correct 125 ms 69276 KB Output is correct
7 Correct 123 ms 69288 KB Output is correct
8 Correct 32 ms 66076 KB Output is correct
9 Correct 33 ms 66088 KB Output is correct
10 Correct 28 ms 66000 KB Output is correct
11 Correct 239 ms 76888 KB Output is correct
12 Correct 258 ms 76908 KB Output is correct
13 Correct 242 ms 77112 KB Output is correct
14 Correct 245 ms 77196 KB Output is correct
15 Correct 241 ms 77152 KB Output is correct
16 Correct 246 ms 76760 KB Output is correct
17 Correct 237 ms 76812 KB Output is correct
18 Correct 240 ms 76812 KB Output is correct
19 Incorrect 28 ms 66048 KB Output isn't correct
20 Halted 0 ms 0 KB -