oj.uz

Submission #585102

# Submission time Handle Problem Language Result Execution time Memory
585102 2022-06-28T10:06:01 Z GioChkhaidze Progression (NOI20_progression) C++14
61 / 100
 3000 ms 67204 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 > 1000) {
					
				--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 3095 ms 53432 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 33204 KB Output is correct
2 Correct 17 ms 33108 KB Output is correct
3 Correct 16 ms 33168 KB Output is correct
4 Correct 15 ms 33128 KB Output is correct
5 Correct 15 ms 33144 KB Output is correct
6 Correct 15 ms 33188 KB Output is correct
7 Correct 15 ms 33120 KB Output is correct
8 Correct 61 ms 33216 KB Output is correct
9 Correct 67 ms 33200 KB Output is correct
10 Correct 53 ms 33208 KB Output is correct
11 Correct 31 ms 33108 KB Output is correct
12 Correct 59 ms 33108 KB Output is correct
13 Correct 33 ms 33200 KB Output is correct
14 Correct 32 ms 33108 KB Output is correct
15 Correct 58 ms 33208 KB Output is correct
16 Correct 61 ms 33216 KB Output is correct
17 Correct 60 ms 33200 KB Output is correct
18 Correct 61 ms 33108 KB Output is correct
19 Correct 18 ms 33212 KB Output is correct
20 Correct 18 ms 33132 KB Output is correct
21 Correct 16 ms 33112 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 36556 KB Output is correct
2 Correct 111 ms 33780 KB Output is correct
3 Correct 120 ms 33744 KB Output is correct
4 Correct 100 ms 33780 KB Output is correct
5 Correct 119 ms 33848 KB Output is correct
6 Correct 126 ms 33868 KB Output is correct
7 Correct 118 ms 33800 KB Output is correct
8 Correct 15 ms 33108 KB Output is correct
9 Correct 15 ms 33124 KB Output is correct
10 Correct 16 ms 33108 KB Output is correct
11 Correct 303 ms 36268 KB Output is correct
12 Correct 280 ms 36676 KB Output is correct
13 Correct 308 ms 36520 KB Output is correct
14 Correct 289 ms 36312 KB Output is correct
15 Correct 315 ms 36632 KB Output is correct
16 Correct 295 ms 37012 KB Output is correct
17 Correct 341 ms 36872 KB Output is correct
18 Correct 300 ms 36928 KB Output is correct
19 Correct 305 ms 36320 KB Output is correct
20 Correct 273 ms 36120 KB Output is correct
21 Correct 292 ms 36392 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 35776 KB Output is correct
2 Correct 157 ms 33360 KB Output is correct
3 Correct 142 ms 33388 KB Output is correct
4 Correct 130 ms 33276 KB Output is correct
5 Correct 135 ms 33312 KB Output is correct
6 Correct 130 ms 33476 KB Output is correct
7 Correct 138 ms 33360 KB Output is correct
8 Correct 16 ms 33180 KB Output is correct
9 Correct 15 ms 33108 KB Output is correct
10 Correct 15 ms 33108 KB Output is correct
11 Correct 439 ms 35940 KB Output is correct
12 Correct 416 ms 35720 KB Output is correct
13 Correct 412 ms 35976 KB Output is correct
14 Correct 428 ms 35748 KB Output is correct
15 Correct 377 ms 35676 KB Output is correct
16 Correct 405 ms 35776 KB Output is correct
17 Correct 421 ms 35728 KB Output is correct
18 Correct 422 ms 35808 KB Output is correct
19 Correct 419 ms 35756 KB Output is correct
20 Correct 419 ms 36044 KB Output is correct
21 Correct 416 ms 35856 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 36556 KB Output is correct
2 Correct 111 ms 33780 KB Output is correct
3 Correct 120 ms 33744 KB Output is correct
4 Correct 100 ms 33780 KB Output is correct
5 Correct 119 ms 33848 KB Output is correct
6 Correct 126 ms 33868 KB Output is correct
7 Correct 118 ms 33800 KB Output is correct
8 Correct 15 ms 33108 KB Output is correct
9 Correct 15 ms 33124 KB Output is correct
10 Correct 16 ms 33108 KB Output is correct
11 Correct 303 ms 36268 KB Output is correct
12 Correct 280 ms 36676 KB Output is correct
13 Correct 308 ms 36520 KB Output is correct
14 Correct 289 ms 36312 KB Output is correct
15 Correct 315 ms 36632 KB Output is correct
16 Correct 295 ms 37012 KB Output is correct
17 Correct 341 ms 36872 KB Output is correct
18 Correct 300 ms 36928 KB Output is correct
19 Correct 305 ms 36320 KB Output is correct
20 Correct 273 ms 36120 KB Output is correct
21 Correct 292 ms 36392 KB Output is correct
22 Incorrect 1834 ms 67204 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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