oj.uz

Submission #585214

# Submission time Handle Problem Language Result Execution time Memory
585214 2022-06-28T12:38:53 Z GioChkhaidze Progression (NOI20_progression) C++14
57 / 100
 770 ms 75764 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;
	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 (1 < L) {
				id = L - 1;
				b[id] = S - Avl(id); 
				up_dot(1, 1, m);
			}

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

			if (R < n) {
				id = R;
				b[id] = Avl(id + 1) - (S + (R - L) * C); 
				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 256 ms 73428 KB Output is correct
2 Correct 177 ms 66372 KB Output is correct
3 Correct 119 ms 66380 KB Output is correct
4 Correct 122 ms 66336 KB Output is correct
5 Correct 121 ms 66336 KB Output is correct
6 Correct 119 ms 66384 KB Output is correct
7 Correct 119 ms 66400 KB Output is correct
8 Correct 32 ms 66016 KB Output is correct
9 Correct 32 ms 66092 KB Output is correct
10 Correct 30 ms 65984 KB Output is correct
11 Correct 241 ms 73752 KB Output is correct
12 Correct 251 ms 73676 KB Output is correct
13 Correct 239 ms 74092 KB Output is correct
14 Correct 250 ms 74192 KB Output is correct
15 Correct 241 ms 74080 KB Output is correct
16 Correct 239 ms 73804 KB Output is correct
17 Correct 250 ms 73800 KB Output is correct
18 Correct 243 ms 73684 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 66020 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 297 ms 71956 KB Output is correct
2 Correct 137 ms 66760 KB Output is correct
3 Correct 117 ms 66716 KB Output is correct
4 Correct 103 ms 66756 KB Output is correct
5 Correct 113 ms 66936 KB Output is correct
6 Correct 112 ms 66764 KB Output is correct
7 Correct 117 ms 66852 KB Output is correct
8 Correct 29 ms 65972 KB Output is correct
9 Correct 33 ms 66028 KB Output is correct
10 Correct 28 ms 66004 KB Output is correct
11 Correct 297 ms 73804 KB Output is correct
12 Correct 289 ms 74240 KB Output is correct
13 Correct 344 ms 73932 KB Output is correct
14 Correct 313 ms 73944 KB Output is correct
15 Correct 277 ms 74188 KB Output is correct
16 Correct 334 ms 74592 KB Output is correct
17 Correct 301 ms 74528 KB Output is correct
18 Correct 316 ms 74588 KB Output is correct
19 Correct 290 ms 73928 KB Output is correct
20 Correct 274 ms 73828 KB Output is correct
21 Correct 285 ms 73900 KB Output is correct

Subtask #4
0 / 11.0

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

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 71956 KB Output is correct
2 Correct 137 ms 66760 KB Output is correct
3 Correct 117 ms 66716 KB Output is correct
4 Correct 103 ms 66756 KB Output is correct
5 Correct 113 ms 66936 KB Output is correct
6 Correct 112 ms 66764 KB Output is correct
7 Correct 117 ms 66852 KB Output is correct
8 Correct 29 ms 65972 KB Output is correct
9 Correct 33 ms 66028 KB Output is correct
10 Correct 28 ms 66004 KB Output is correct
11 Correct 297 ms 73804 KB Output is correct
12 Correct 289 ms 74240 KB Output is correct
13 Correct 344 ms 73932 KB Output is correct
14 Correct 313 ms 73944 KB Output is correct
15 Correct 277 ms 74188 KB Output is correct
16 Correct 334 ms 74592 KB Output is correct
17 Correct 301 ms 74528 KB Output is correct
18 Correct 316 ms 74588 KB Output is correct
19 Correct 290 ms 73928 KB Output is correct
20 Correct 274 ms 73828 KB Output is correct
21 Correct 285 ms 73900 KB Output is correct
22 Correct 696 ms 75580 KB Output is correct
23 Correct 180 ms 68324 KB Output is correct
24 Correct 165 ms 68452 KB Output is correct
25 Correct 165 ms 68324 KB Output is correct
26 Correct 180 ms 68344 KB Output is correct
27 Correct 170 ms 68416 KB Output is correct
28 Correct 164 ms 68372 KB Output is correct
29 Correct 29 ms 65996 KB Output is correct
30 Correct 31 ms 66076 KB Output is correct
31 Correct 28 ms 66044 KB Output is correct
32 Correct 738 ms 75308 KB Output is correct
33 Correct 700 ms 75292 KB Output is correct
34 Correct 770 ms 75584 KB Output is correct
35 Correct 698 ms 75472 KB Output is correct
36 Correct 543 ms 75764 KB Output is correct
37 Correct 552 ms 75672 KB Output is correct
38 Correct 554 ms 75596 KB Output is correct
39 Correct 692 ms 75424 KB Output is correct
40 Correct 711 ms 75204 KB Output is correct
41 Correct 754 ms 75292 KB Output is correct
42 Correct 716 ms 75396 KB Output is correct
43 Correct 710 ms 75424 KB Output is correct
44 Correct 682 ms 75624 KB Output is correct
45 Correct 681 ms 75684 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 73428 KB Output is correct
2 Correct 177 ms 66372 KB Output is correct
3 Correct 119 ms 66380 KB Output is correct
4 Correct 122 ms 66336 KB Output is correct
5 Correct 121 ms 66336 KB Output is correct
6 Correct 119 ms 66384 KB Output is correct
7 Correct 119 ms 66400 KB Output is correct
8 Correct 32 ms 66016 KB Output is correct
9 Correct 32 ms 66092 KB Output is correct
10 Correct 30 ms 65984 KB Output is correct
11 Correct 241 ms 73752 KB Output is correct
12 Correct 251 ms 73676 KB Output is correct
13 Correct 239 ms 74092 KB Output is correct
14 Correct 250 ms 74192 KB Output is correct
15 Correct 241 ms 74080 KB Output is correct
16 Correct 239 ms 73804 KB Output is correct
17 Correct 250 ms 73800 KB Output is correct
18 Correct 243 ms 73684 KB Output is correct
19 Incorrect 30 ms 66020 KB Output isn't correct
20 Halted 0 ms 0 KB -