oj.uz

Submission #585058

# Submission time Handle Problem Language Result Execution time Memory
585058 2022-06-28T09:34:11 Z GioChkhaidze Progression (NOI20_progression) C++14
61 / 100
 3000 ms 45572 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, 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) {
	
}

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_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]);
}

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);
	for (int i = 1; i <= q; ++i) {
		int tp;
		cin >> tp >> L >> R;
		if (tp == 1) {
			cin >> S >> C;
			ll vl = S;
			for (int j = L; j <= R; ++j) {
				change_id(j, a[j] + vl);
				vl += C;
			}
		}
			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 3032 ms 35688 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 33236 KB Output is correct
2 Correct 15 ms 33108 KB Output is correct
3 Correct 15 ms 33212 KB Output is correct
4 Correct 16 ms 33120 KB Output is correct
5 Correct 15 ms 33108 KB Output is correct
6 Correct 15 ms 33120 KB Output is correct
7 Correct 17 ms 33108 KB Output is correct
8 Correct 53 ms 33212 KB Output is correct
9 Correct 51 ms 33236 KB Output is correct
10 Correct 51 ms 33216 KB Output is correct
11 Correct 29 ms 33196 KB Output is correct
12 Correct 53 ms 33228 KB Output is correct
13 Correct 29 ms 33236 KB Output is correct
14 Correct 29 ms 33172 KB Output is correct
15 Correct 51 ms 33236 KB Output is correct
16 Correct 53 ms 33220 KB Output is correct
17 Correct 55 ms 33236 KB Output is correct
18 Correct 54 ms 33236 KB Output is correct
19 Correct 16 ms 33192 KB Output is correct
20 Correct 15 ms 33108 KB Output is correct
21 Correct 17 ms 33212 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 36788 KB Output is correct
2 Correct 110 ms 34016 KB Output is correct
3 Correct 109 ms 34052 KB Output is correct
4 Correct 95 ms 33940 KB Output is correct
5 Correct 103 ms 34204 KB Output is correct
6 Correct 104 ms 34088 KB Output is correct
7 Correct 107 ms 34092 KB Output is correct
8 Correct 15 ms 33108 KB Output is correct
9 Correct 14 ms 33108 KB Output is correct
10 Correct 15 ms 33108 KB Output is correct
11 Correct 277 ms 36484 KB Output is correct
12 Correct 266 ms 36796 KB Output is correct
13 Correct 274 ms 36556 KB Output is correct
14 Correct 274 ms 36592 KB Output is correct
15 Correct 270 ms 36800 KB Output is correct
16 Correct 288 ms 37292 KB Output is correct
17 Correct 279 ms 37244 KB Output is correct
18 Correct 283 ms 37200 KB Output is correct
19 Correct 253 ms 36472 KB Output is correct
20 Correct 259 ms 36428 KB Output is correct
21 Correct 262 ms 36384 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 36064 KB Output is correct
2 Correct 121 ms 36532 KB Output is correct
3 Correct 122 ms 36560 KB Output is correct
4 Correct 121 ms 36532 KB Output is correct
5 Correct 121 ms 36544 KB Output is correct
6 Correct 120 ms 36556 KB Output is correct
7 Correct 120 ms 36528 KB Output is correct
8 Correct 14 ms 33108 KB Output is correct
9 Correct 15 ms 33140 KB Output is correct
10 Correct 14 ms 33216 KB Output is correct
11 Correct 378 ms 42092 KB Output is correct
12 Correct 385 ms 45312 KB Output is correct
13 Correct 378 ms 42084 KB Output is correct
14 Correct 367 ms 42112 KB Output is correct
15 Correct 368 ms 45284 KB Output is correct
16 Correct 393 ms 45572 KB Output is correct
17 Correct 391 ms 45380 KB Output is correct
18 Correct 393 ms 45568 KB Output is correct
19 Correct 386 ms 45328 KB Output is correct
20 Correct 370 ms 45392 KB Output is correct
21 Correct 378 ms 45412 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 36788 KB Output is correct
2 Correct 110 ms 34016 KB Output is correct
3 Correct 109 ms 34052 KB Output is correct
4 Correct 95 ms 33940 KB Output is correct
5 Correct 103 ms 34204 KB Output is correct
6 Correct 104 ms 34088 KB Output is correct
7 Correct 107 ms 34092 KB Output is correct
8 Correct 15 ms 33108 KB Output is correct
9 Correct 14 ms 33108 KB Output is correct
10 Correct 15 ms 33108 KB Output is correct
11 Correct 277 ms 36484 KB Output is correct
12 Correct 266 ms 36796 KB Output is correct
13 Correct 274 ms 36556 KB Output is correct
14 Correct 274 ms 36592 KB Output is correct
15 Correct 270 ms 36800 KB Output is correct
16 Correct 288 ms 37292 KB Output is correct
17 Correct 279 ms 37244 KB Output is correct
18 Correct 283 ms 37200 KB Output is correct
19 Correct 253 ms 36472 KB Output is correct
20 Correct 259 ms 36428 KB Output is correct
21 Correct 262 ms 36384 KB Output is correct
22 Execution timed out 3073 ms 35672 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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