oj.uz

Submission #585105

# Submission time Handle Problem Language Result Execution time Memory
585105 2022-06-28T10:07:35 Z GioChkhaidze Progression (NOI20_progression) C++14
48 / 100
 3000 ms 44964 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;

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

struct node {
	int ans;
	int len;
	int fr;
	int ls;
	int pr;
	int sf;
	int add;
	node () {
		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);
	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].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].add += v[h].add;
		v[rf].add += v[h].add;
		v[h].add = 0;
	}
}

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 = 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].add += C;
		v[h].fr += C;
		v[h].ls += 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 = b[l];
		return;
	}
	shift(h, l, r);
	if (id <= mf) {
		up_dot(left);
	}
		else {
		up_dot(right);
	}
	v[h] = mrg(v[lf], v[rf]);
}

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));
}

void change_id(int x, int vl) {
	a[x] = vl;
	if (1 < x) {
		id = x - 1;
		b[id] = a[id + 1] - a[id];
		up_dot(1, 1, m);
	}
	
	if (x < n) {
		id = x;
		b[id] = a[id + 1] - a[id];
		up_dot(1, 1, m);
	}
}

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);

	/*cout << "\n";
	for (int j = 1; j < n; ++j) {
	id = j; cout << get_vl(1, 1, m) << " ";
	}
	cout << "\n";*/

	for (int i = 1; i <= q; ++i) {
		int tp;
		cin >> tp >> L >> R;
		if (tp == 1) {
			cin >> S >> C;

				--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);
				}

				/*cout << "\n";
				for (int j = 1; j < n; ++j) {
					id = j, cout << get_vl(1, 1, m) << " ";
				}
				cout << "\n";*/


			/*
			a[L - 1] += S
			b[L - 1] = a[L] - a[L - 1]
			b[R] = a[R + 1] - a[R]
			*/
		}
			else
		if (tp == 2) {
			cin >> S >> C;
			ll vl = S;
			for (int j = L; j <= R; ++j) {
				change_id(j, vl);
				vl += C;
			}
		}
			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]



QUERY ADD
QUERY PUT
QUERY 




*/

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3081 ms 35796 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 33188 KB Output is correct
2 Incorrect 16 ms 33184 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 36476 KB Output is correct
2 Correct 112 ms 33788 KB Output is correct
3 Correct 107 ms 33740 KB Output is correct
4 Correct 102 ms 33784 KB Output is correct
5 Correct 111 ms 33820 KB Output is correct
6 Correct 110 ms 33884 KB Output is correct
7 Correct 115 ms 33776 KB Output is correct
8 Correct 20 ms 33108 KB Output is correct
9 Correct 18 ms 33156 KB Output is correct
10 Correct 22 ms 33136 KB Output is correct
11 Correct 287 ms 36324 KB Output is correct
12 Correct 285 ms 36512 KB Output is correct
13 Correct 302 ms 36220 KB Output is correct
14 Correct 297 ms 36388 KB Output is correct
15 Correct 282 ms 36468 KB Output is correct
16 Correct 307 ms 36792 KB Output is correct
17 Correct 314 ms 36860 KB Output is correct
18 Correct 360 ms 36892 KB Output is correct
19 Correct 304 ms 36200 KB Output is correct
20 Correct 287 ms 36216 KB Output is correct
21 Correct 297 ms 36172 KB Output is correct

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 518 ms 35792 KB Output is correct
2 Incorrect 152 ms 33308 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 306 ms 36476 KB Output is correct
2 Correct 112 ms 33788 KB Output is correct
3 Correct 107 ms 33740 KB Output is correct
4 Correct 102 ms 33784 KB Output is correct
5 Correct 111 ms 33820 KB Output is correct
6 Correct 110 ms 33884 KB Output is correct
7 Correct 115 ms 33776 KB Output is correct
8 Correct 20 ms 33108 KB Output is correct
9 Correct 18 ms 33156 KB Output is correct
10 Correct 22 ms 33136 KB Output is correct
11 Correct 287 ms 36324 KB Output is correct
12 Correct 285 ms 36512 KB Output is correct
13 Correct 302 ms 36220 KB Output is correct
14 Correct 297 ms 36388 KB Output is correct
15 Correct 282 ms 36468 KB Output is correct
16 Correct 307 ms 36792 KB Output is correct
17 Correct 314 ms 36860 KB Output is correct
18 Correct 360 ms 36892 KB Output is correct
19 Correct 304 ms 36200 KB Output is correct
20 Correct 287 ms 36216 KB Output is correct
21 Correct 297 ms 36172 KB Output is correct
22 Correct 740 ms 35908 KB Output is correct
23 Correct 175 ms 36384 KB Output is correct
24 Correct 180 ms 36408 KB Output is correct
25 Correct 175 ms 36444 KB Output is correct
26 Correct 163 ms 36536 KB Output is correct
27 Correct 172 ms 36468 KB Output is correct
28 Correct 180 ms 36464 KB Output is correct
29 Correct 23 ms 33172 KB Output is correct
30 Correct 16 ms 33208 KB Output is correct
31 Correct 17 ms 33176 KB Output is correct
32 Correct 756 ms 41960 KB Output is correct
33 Correct 658 ms 44756 KB Output is correct
34 Correct 656 ms 42020 KB Output is correct
35 Correct 679 ms 42176 KB Output is correct
36 Correct 530 ms 41848 KB Output is correct
37 Correct 569 ms 41964 KB Output is correct
38 Correct 558 ms 42000 KB Output is correct
39 Correct 676 ms 44856 KB Output is correct
40 Correct 664 ms 44916 KB Output is correct
41 Correct 693 ms 44964 KB Output is correct
42 Correct 666 ms 44812 KB Output is correct
43 Correct 654 ms 44804 KB Output is correct
44 Correct 679 ms 44828 KB Output is correct
45 Correct 641 ms 44748 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3081 ms 35796 KB Time limit exceeded
2 Halted 0 ms 0 KB -