제출 #585102

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
585102		GioChkhaidze	Progression (NOI20_progression)	C++14	61 / 100	3095 ms	67204 KiB

Progression

// 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
• Subtask 2: 15 / 15
• Subtask 3: 35 / 35
• Subtask 4: 11 / 11
• Subtask 5: 0 / 13
• Subtask 6: 0 / 17