oj.uz

Submission #585242

# Submission time Handle Problem Language Result Execution time Memory
585242 2022-06-28T13:09:25 Z keta_tsimakuridze Progression (NOI20_progression) C++17
15 / 100
 170 ms 108308 KB 
#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 = 2e5 + 5, mod = 1e9 + 7, inf = 1e18; //!
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[N];
bool eq(int a, int b) {
	return (a == -inf || b == -inf ? 1 : a == b);
}
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);
//	cout << eq(a.suf.f, b.suf.f) << endl;
	if(eq(a.suf.f, b.pref.f) && eq(a.suf.f, b.L - a.R) && eq(b.pref.f, b.L - a.R)) {
		c.ans = max(c.ans, a.suf.s + b.pref.s);
	}
	if(eq(a.suf.f, b.L - a.R)) {
		c.ans = max(c.ans, a.suf.s + 1);
	}
	if(eq(b.pref.f, b.L - a.R)) {
		c.ans = max(c.ans, b.pref.s + 1);
	}
	c.suf = b.suf;
	if(b.suf.s == b.len && eq(a.suf.f, b.pref.f) && eq(a.suf.f, b.L - a.R) && eq(b.suf.f, b.L - a.R)) {
		c.suf.s += a.suf.s;
	} else if(b.suf.s == b.len && eq(b.suf.f, b.L - a.R)) {
		c.suf.s++;
	}
	c.pref = a.pref;
	if(a.pref.s == a.len && eq(a.pref.f, b.pref.f)&& eq(a.pref.f, b.L - a.R) && eq(b.pref.f, b.L - a.R)) {
		c.pref.s += b.pref.s;
	} else if(a.pref.s == a.len && eq(a.pref.f, b.L - a.R)) c.pref.s++;
	
	if(b.len == 1) {
		c.suf.f = b.L - a.R;
	}
	if(a.len == 1) {
		c.pref.f = b.L - a.R;
	}
	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 = {-inf, 1};
		tree[u].suf = {-inf, 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 ? -inf : 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

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

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 157 ms 108308 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 50348 KB Output is correct
2 Correct 22 ms 50388 KB Output is correct
3 Correct 26 ms 50364 KB Output is correct
4 Correct 26 ms 50388 KB Output is correct
5 Correct 25 ms 50388 KB Output is correct
6 Correct 20 ms 50404 KB Output is correct
7 Correct 20 ms 50388 KB Output is correct
8 Correct 21 ms 50388 KB Output is correct
9 Correct 21 ms 50376 KB Output is correct
10 Correct 26 ms 50396 KB Output is correct
11 Correct 23 ms 50388 KB Output is correct
12 Correct 24 ms 50388 KB Output is correct
13 Correct 23 ms 50360 KB Output is correct
14 Correct 22 ms 50372 KB Output is correct
15 Correct 22 ms 50388 KB Output is correct
16 Correct 21 ms 50344 KB Output is correct
17 Correct 22 ms 50408 KB Output is correct
18 Correct 21 ms 50420 KB Output is correct
19 Correct 21 ms 50388 KB Output is correct
20 Correct 21 ms 50304 KB Output is correct
21 Correct 22 ms 50388 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 170 ms 108260 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 155 ms 108268 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 170 ms 108260 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 157 ms 108308 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -