oj.uz

Submission #585100

# Submission time Handle Problem Language Result Execution time Memory
585100 2022-06-28T10:04:33 Z GioChkhaidze Progression (NOI20_progression) C++14
61 / 100
 3000 ms 66640 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;
		cout << l << " " << r << "\n";
		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;
			if (R - L + 1 > 2000) {
					
				--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";*/
			}
				else {
				ll vl = S;
				for (int j = L; j <= R; ++j) {
					change_id(j, a[j] + vl);
					vl += C;
				}
			}

			/*
			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 3062 ms 55060 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 33196 KB Output is correct
2 Correct 16 ms 33216 KB Output is correct
3 Correct 16 ms 33108 KB Output is correct
4 Correct 16 ms 33208 KB Output is correct
5 Correct 15 ms 33172 KB Output is correct
6 Correct 16 ms 33108 KB Output is correct
7 Correct 16 ms 33152 KB Output is correct
8 Correct 59 ms 33108 KB Output is correct
9 Correct 56 ms 33216 KB Output is correct
10 Correct 54 ms 33216 KB Output is correct
11 Correct 35 ms 33108 KB Output is correct
12 Correct 58 ms 33236 KB Output is correct
13 Correct 33 ms 33216 KB Output is correct
14 Correct 35 ms 33216 KB Output is correct
15 Correct 59 ms 33236 KB Output is correct
16 Correct 59 ms 33236 KB Output is correct
17 Correct 60 ms 33224 KB Output is correct
18 Correct 66 ms 33224 KB Output is correct
19 Correct 20 ms 33200 KB Output is correct
20 Correct 18 ms 33236 KB Output is correct
21 Correct 17 ms 33204 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 36560 KB Output is correct
2 Correct 112 ms 34996 KB Output is correct
3 Correct 109 ms 35044 KB Output is correct
4 Correct 96 ms 34976 KB Output is correct
5 Correct 117 ms 35148 KB Output is correct
6 Correct 113 ms 35136 KB Output is correct
7 Correct 111 ms 35128 KB Output is correct
8 Correct 16 ms 33108 KB Output is correct
9 Correct 16 ms 33108 KB Output is correct
10 Correct 15 ms 33216 KB Output is correct
11 Correct 280 ms 37576 KB Output is correct
12 Correct 281 ms 37964 KB Output is correct
13 Correct 318 ms 37624 KB Output is correct
14 Correct 296 ms 37732 KB Output is correct
15 Correct 288 ms 37728 KB Output is correct
16 Correct 288 ms 38128 KB Output is correct
17 Correct 288 ms 38316 KB Output is correct
18 Correct 301 ms 38196 KB Output is correct
19 Correct 268 ms 37552 KB Output is correct
20 Correct 268 ms 37516 KB Output is correct
21 Correct 277 ms 37432 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 400 ms 35796 KB Output is correct
2 Correct 133 ms 36536 KB Output is correct
3 Correct 126 ms 36556 KB Output is correct
4 Correct 127 ms 36604 KB Output is correct
5 Correct 129 ms 36536 KB Output is correct
6 Correct 131 ms 36676 KB Output is correct
7 Correct 149 ms 36560 KB Output is correct
8 Correct 15 ms 33108 KB Output is correct
9 Correct 15 ms 33200 KB Output is correct
10 Correct 15 ms 33180 KB Output is correct
11 Correct 425 ms 39384 KB Output is correct
12 Correct 388 ms 38996 KB Output is correct
13 Correct 391 ms 39392 KB Output is correct
14 Correct 391 ms 39372 KB Output is correct
15 Correct 378 ms 38932 KB Output is correct
16 Correct 422 ms 38984 KB Output is correct
17 Correct 418 ms 38908 KB Output is correct
18 Correct 445 ms 38884 KB Output is correct
19 Correct 396 ms 38928 KB Output is correct
20 Correct 420 ms 39060 KB Output is correct
21 Correct 395 ms 38960 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 36560 KB Output is correct
2 Correct 112 ms 34996 KB Output is correct
3 Correct 109 ms 35044 KB Output is correct
4 Correct 96 ms 34976 KB Output is correct
5 Correct 117 ms 35148 KB Output is correct
6 Correct 113 ms 35136 KB Output is correct
7 Correct 111 ms 35128 KB Output is correct
8 Correct 16 ms 33108 KB Output is correct
9 Correct 16 ms 33108 KB Output is correct
10 Correct 15 ms 33216 KB Output is correct
11 Correct 280 ms 37576 KB Output is correct
12 Correct 281 ms 37964 KB Output is correct
13 Correct 318 ms 37624 KB Output is correct
14 Correct 296 ms 37732 KB Output is correct
15 Correct 288 ms 37728 KB Output is correct
16 Correct 288 ms 38128 KB Output is correct
17 Correct 288 ms 38316 KB Output is correct
18 Correct 301 ms 38196 KB Output is correct
19 Correct 268 ms 37552 KB Output is correct
20 Correct 268 ms 37516 KB Output is correct
21 Correct 277 ms 37432 KB Output is correct
22 Execution timed out 3053 ms 66640 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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