oj.uz

Submission #585211

# Submission time Handle Problem Language Result Execution time Memory
585211 2022-06-28T12:36:26 Z GioChkhaidze Progression (NOI20_progression) C++14
0 / 100
 630 ms 1048576 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) assert(v[h].add == 0), v[h].toggle += C;
			else assert(v[h].toggle == 0), 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 - 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 (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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 71324 KB Output is correct
2 Correct 98 ms 66360 KB Output is correct
3 Correct 98 ms 66372 KB Output is correct
4 Correct 109 ms 66352 KB Output is correct
5 Correct 103 ms 66396 KB Output is correct
6 Correct 100 ms 66440 KB Output is correct
7 Correct 98 ms 66380 KB Output is correct
8 Runtime error 630 ms 1048576 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

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

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 73620 KB Output is correct
2 Correct 117 ms 67676 KB Output is correct
3 Correct 116 ms 67660 KB Output is correct
4 Correct 123 ms 67648 KB Output is correct
5 Correct 113 ms 67808 KB Output is correct
6 Correct 115 ms 67924 KB Output is correct
7 Correct 113 ms 67804 KB Output is correct
8 Runtime error 428 ms 1048576 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 73620 KB Output is correct
2 Correct 117 ms 67676 KB Output is correct
3 Correct 116 ms 67660 KB Output is correct
4 Correct 123 ms 67648 KB Output is correct
5 Correct 113 ms 67808 KB Output is correct
6 Correct 115 ms 67924 KB Output is correct
7 Correct 113 ms 67804 KB Output is correct
8 Runtime error 428 ms 1048576 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 71324 KB Output is correct
2 Correct 98 ms 66360 KB Output is correct
3 Correct 98 ms 66372 KB Output is correct
4 Correct 109 ms 66352 KB Output is correct
5 Correct 103 ms 66396 KB Output is correct
6 Correct 100 ms 66440 KB Output is correct
7 Correct 98 ms 66380 KB Output is correct
8 Runtime error 630 ms 1048576 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -