oj.uz

답안 #585215

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
585215 2022-06-28T12:39:27 Z GioChkhaidze Progression (NOI20_progression) C++14
57 / 100
 767 ms 72168 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)  v[h].toggle += C;
			else 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
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 231 ms 71396 KB Output is correct
2 Correct 122 ms 66372 KB Output is correct
3 Correct 125 ms 66288 KB Output is correct
4 Correct 129 ms 66336 KB Output is correct
5 Correct 122 ms 66380 KB Output is correct
6 Correct 123 ms 66376 KB Output is correct
7 Correct 123 ms 66372 KB Output is correct
8 Correct 28 ms 65952 KB Output is correct
9 Correct 30 ms 65992 KB Output is correct
10 Correct 34 ms 66072 KB Output is correct
11 Correct 230 ms 71376 KB Output is correct
12 Correct 231 ms 71300 KB Output is correct
13 Correct 235 ms 71568 KB Output is correct
14 Correct 236 ms 71700 KB Output is correct
15 Correct 231 ms 71560 KB Output is correct
16 Correct 250 ms 71288 KB Output is correct
17 Correct 232 ms 71256 KB Output is correct
18 Correct 231 ms 71260 KB Output is correct

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 30 ms 66000 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 295 ms 71768 KB Output is correct
2 Correct 116 ms 66640 KB Output is correct
3 Correct 127 ms 66688 KB Output is correct
4 Correct 107 ms 66656 KB Output is correct
5 Correct 144 ms 66692 KB Output is correct
6 Correct 117 ms 66668 KB Output is correct
7 Correct 122 ms 66728 KB Output is correct
8 Correct 29 ms 66072 KB Output is correct
9 Correct 31 ms 66004 KB Output is correct
10 Correct 29 ms 66004 KB Output is correct
11 Correct 305 ms 71508 KB Output is correct
12 Correct 276 ms 71824 KB Output is correct
13 Correct 300 ms 71556 KB Output is correct
14 Correct 293 ms 71608 KB Output is correct
15 Correct 292 ms 71720 KB Output is correct
16 Correct 302 ms 72104 KB Output is correct
17 Correct 317 ms 72028 KB Output is correct
18 Correct 296 ms 72168 KB Output is correct
19 Correct 278 ms 71524 KB Output is correct
20 Correct 288 ms 71388 KB Output is correct
21 Correct 280 ms 71348 KB Output is correct

Subtask #4
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 584 ms 71040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 295 ms 71768 KB Output is correct
2 Correct 116 ms 66640 KB Output is correct
3 Correct 127 ms 66688 KB Output is correct
4 Correct 107 ms 66656 KB Output is correct
5 Correct 144 ms 66692 KB Output is correct
6 Correct 117 ms 66668 KB Output is correct
7 Correct 122 ms 66728 KB Output is correct
8 Correct 29 ms 66072 KB Output is correct
9 Correct 31 ms 66004 KB Output is correct
10 Correct 29 ms 66004 KB Output is correct
11 Correct 305 ms 71508 KB Output is correct
12 Correct 276 ms 71824 KB Output is correct
13 Correct 300 ms 71556 KB Output is correct
14 Correct 293 ms 71608 KB Output is correct
15 Correct 292 ms 71720 KB Output is correct
16 Correct 302 ms 72104 KB Output is correct
17 Correct 317 ms 72028 KB Output is correct
18 Correct 296 ms 72168 KB Output is correct
19 Correct 278 ms 71524 KB Output is correct
20 Correct 288 ms 71388 KB Output is correct
21 Correct 280 ms 71348 KB Output is correct
22 Correct 691 ms 71232 KB Output is correct
23 Correct 167 ms 66360 KB Output is correct
24 Correct 162 ms 66264 KB Output is correct
25 Correct 164 ms 66256 KB Output is correct
26 Correct 163 ms 66368 KB Output is correct
27 Correct 163 ms 66264 KB Output is correct
28 Correct 176 ms 66340 KB Output is correct
29 Correct 28 ms 65992 KB Output is correct
30 Correct 28 ms 66080 KB Output is correct
31 Correct 28 ms 66040 KB Output is correct
32 Correct 690 ms 71148 KB Output is correct
33 Correct 767 ms 71244 KB Output is correct
34 Correct 697 ms 71196 KB Output is correct
35 Correct 732 ms 71292 KB Output is correct
36 Correct 547 ms 71416 KB Output is correct
37 Correct 550 ms 71504 KB Output is correct
38 Correct 535 ms 71500 KB Output is correct
39 Correct 684 ms 71088 KB Output is correct
40 Correct 755 ms 71292 KB Output is correct
41 Correct 705 ms 71160 KB Output is correct
42 Correct 706 ms 71248 KB Output is correct
43 Correct 688 ms 71224 KB Output is correct
44 Correct 667 ms 71060 KB Output is correct
45 Correct 721 ms 71180 KB Output is correct

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 231 ms 71396 KB Output is correct
2 Correct 122 ms 66372 KB Output is correct
3 Correct 125 ms 66288 KB Output is correct
4 Correct 129 ms 66336 KB Output is correct
5 Correct 122 ms 66380 KB Output is correct
6 Correct 123 ms 66376 KB Output is correct
7 Correct 123 ms 66372 KB Output is correct
8 Correct 28 ms 65952 KB Output is correct
9 Correct 30 ms 65992 KB Output is correct
10 Correct 34 ms 66072 KB Output is correct
11 Correct 230 ms 71376 KB Output is correct
12 Correct 231 ms 71300 KB Output is correct
13 Correct 235 ms 71568 KB Output is correct
14 Correct 236 ms 71700 KB Output is correct
15 Correct 231 ms 71560 KB Output is correct
16 Correct 250 ms 71288 KB Output is correct
17 Correct 232 ms 71256 KB Output is correct
18 Correct 231 ms 71260 KB Output is correct
19 Incorrect 30 ms 66000 KB Output isn't correct
20 Halted 0 ms 0 KB -