Submission #585389

#	Time	Username	Problem	Language	Result	Execution time	Memory
585389		keta_tsimakuridze	Progression (NOI20_progression)	C++14	100 / 100	926 ms	108440 KiB

Progression

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define f first
#define s second
#define endl "\n"
const int N = 3e5 + 5, mod = 1e9 + 7; //!
int t, d[N], a[N];
struct node {
	int L, R, len;
	pii suf, pref;
	int ans;
} tree[4 * N];
struct z {
	int k, b, t;
} lazy[4 * N];
bool eq(pii a, pii b) {
	return (min(a.s, b.s) == 1 ? 1 : a.f == b.f);
}
node merge(node a, node b) {
	node c;
	c.len = a.len + b.len;
	c.L = a.L; c.R = b.R;
	c.ans = max(a.ans, b.ans);
	c.pref = a.pref; c.suf = b.suf;
	int d = b.L - a.R;
	if(eq(a.suf, {d, 2})) {
		c.ans = max(c.ans, a.suf.s + (!eq({d, 2}, b.pref) ? 1 : b.pref.s));
	}
	if(eq(b.pref, {d, 2})) {
		c.ans = max(c.ans, b.pref.s + (!eq({d, 2}, a.suf) ? 1 : a.suf.s));
	}
	if(c.suf.s == 1) c.suf.f = d;
	if(c.pref.s == 1) c.pref.f = d;
	if(a.pref.s == a.len && eq(a.pref, {d, 2})) {
		c.pref.s += (eq({d, 2}, b.pref) ? b.pref.s : 1);
	}
	if(b.suf.s == b.len && eq(b.suf, {d, 2})) {
		c.suf.s += (eq({d, 2}, a.suf) ? a.suf.s : 1);
	}
	return c;
		
}
void build(int u,int l,int r) {
	if(l == r) {
		tree[u].L = tree[u].R = a[l];
		tree[u].ans = 1;
		tree[u].pref = {0, 1};
		tree[u].suf = {0, 1};
		tree[u].len = 1;
		return;
	}
	int mid = (l + r) / 2;
	build(2 * u, l, mid); build(2 * u + 1, mid + 1, r);
	tree[u] = merge(tree[2 * u], tree[2 * u + 1]);
//	cout << l << " " << r << " " << tree[u].ans << " " << tree[u].R << " " << tree[u].suf.f << " " << tree[u].suf.s <<endl;
 
}
void push(int u,int l,int r) {
	if(lazy[u].t) {
		tree[u].ans = r - l + 1;
		tree[u].L = lazy[u].k * l + lazy[u].b;
		tree[u].R = lazy[u].k * r + lazy[u].b;
		
		tree[u].pref.s = tree[u].suf.s = r - l + 1;
		tree[u].pref.f = tree[u].suf.f = (r == l ? 0 : lazy[u].k);
		tree[u].ans = r - l + 1;
		if(l != r) {
			lazy[2 * u].t = lazy[2 * u + 1].t = 1;
			lazy[2 * u].k = lazy[2 * u + 1].k = lazy[u].k;
			lazy[2 * u].b = lazy[2 * u + 1].b = lazy[u].b;
		}
	} else {
		tree[u].L += lazy[u].k * l + lazy[u].b;
		tree[u].R += lazy[u].k * r + lazy[u].b;
		if(tree[u].len > 1) {
			tree[u].pref.f += lazy[u].k;
			tree[u].suf.f += lazy[u].k;
		}
		if(l != r) {
			lazy[2 * u].k += lazy[u].k;
			lazy[2 * u + 1].k += lazy[u].k;
			lazy[2 * u].b += lazy[u].b;
			lazy[2 * u + 1].b += lazy[u].b;
		}		
	}
	lazy[u].k = lazy[u].b = lazy[u].t = 0;
}
void upd(int u,int st,int en,int l,int r,int k,int b,int t) {
	push(u, l, r);
	if(l > en || r < st) return;
	if(st <= l && r <= en) {			
		lazy[u].k = k;
		lazy[u].b = b;
		lazy[u].t = (t == 2);
		push(u, l, r);
		return;
	}
	int mid = (l + r) / 2;
	upd(2 * u, st, en, l, mid, k, b, t);
	upd(2 * u + 1, st, en, mid + 1, r, k, b, t);
	tree[u] = merge(tree[2 * u], tree[2 * u + 1]);
}
node get(int u,int st,int en, int l,int r) {
	push(u, l, r);
	if(st <= l && r <= en) return tree[u];
	int mid = (l + r) / 2;
	if(mid + 1 > en) return get(2 * u, st, en, l, mid);
	if(mid < st) return get(2 * u + 1, st, en, mid + 1, r);
	return merge(get(2 * u, st, en, l, mid), get(2 * u + 1, st, en, mid + 1, r));
}
 
main() {
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int n, q;
	cin >> n >> q;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	build(1, 1, n);
	for(int i = 1; i <= q; i++) {
		int t;
		cin >> t;
		if(t < 3) { 
			int l, r, s, c;
			cin >> l >> r >> s >> c; 
 
				upd(1, l, r, 1, n, c, s - l * c, t);
			
 
			continue; 
		}
		int l, r;
		cin >> l >> r;
	//	for(int j = 1; j <= n; j++) a[j] = get(1, j, 1, n);
		cout << get(1, l, r, 1, n).ans << endl;
	}
}

Compilation message (stderr)

Progression.cpp:114:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  114 | main() {
      | ^~~~

• Subtask 1: 9 / 9
• Subtask 2: 15 / 15
• Subtask 3: 35 / 35
• Subtask 4: 11 / 11
• Subtask 5: 13 / 13
• Subtask 6: 17 / 17