UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#203931#555. 积木tkswls100625ms16684kbC++113.1kb2024-03-26 11:36:572024-03-26 12:42:05

answer

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define ld long double
#define int long long
using namespace std;
int l[100005], r[100005], sum[100005], n, ssum[100005];
const int inf = 1000000000000000000;
struct XD {
	int k, b;
};
struct node {
	int l, r;
	XD maxn, minn;
} b[400005];
inline void build(int p, int l, int r) {
	b[p].l = l, b[p].r = r;
	b[p].minn = XD{0, inf}, b[p].maxn = XD{0, -inf};
	if (l == r) return;
	build(2 * p, l, (l + r) >> 1);
	build(2 * p + 1, ((l + r) >> 1) + 1, r);
}
inline int calc(XD p, int q) {
	return p.k * q + p.b;
}
inline void changemax(int p, XD op) {
	int mid = (b[p].l + b[p].r) >> 1;
	if (calc(op, ssum[mid]) > calc(b[p].maxn, ssum[mid])) {
		swap(op, b[p].maxn);
	}
	if (b[p].l == b[p].r) return;
	if (op.k < b[p].maxn.k) changemax(2 * p, op);
	else if (op.k > b[p].maxn.k) changemax(2 * p + 1, op);
}
inline void changemin(int p, XD op) {
	int mid = (b[p].l + b[p].r) >> 1;
	if (calc(op, ssum[mid]) < calc(b[p].minn, ssum[mid])) {
		swap(op, b[p].minn);
	}
	if (b[p].l == b[p].r) return;
	if (op.k < b[p].minn.k) changemin(2 * p + 1, op);
	else if (op.k > b[p].minn.k) changemin(2 * p, op);
}
inline int querymax(int p, int q) {
	if (b[p].l == b[p].r) {
		return calc(b[p].maxn, ssum[q]);
	}
	if (q <= (b[p].l + b[p].r) / 2) {
		return max(calc(b[p].maxn, ssum[q]), querymax(2 * p, q));
	}
	return max(calc(b[p].maxn, ssum[q]), querymax(2 * p + 1, q));
}
inline int querymin(int p, int q) {
	if (b[p].l == b[p].r) {
		return calc(b[p].minn, ssum[q]);
	}
	if (q <= (b[p].l + b[p].r) / 2) {
		return min(calc(b[p].minn, ssum[q]), querymin(2 * p, q));
	}
	return min(calc(b[p].minn, ssum[q]), querymin(2 * p + 1, q));
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> l[i] >> r[i];
	}
	for (int i = 1; 2 * i <= n; i++) {
		swap(l[i], l[n - i + 1]);
		swap(r[i], r[n - i + 1]);
	}
	for (int i = 1; i <= n; i++) {
		l[i] <<= 1, r[i] <<= 1;
		sum[i] = sum[i - 1] + (r[i] - l[i]) / 2 * (r[i] + l[i]);
		ssum[i] = ssum[i - 1] + (r[i] - l[i]);
	}
	build(1, 1, n);
	int ans = -1;
	int lst = 0;
	for (int i = 1; i < n; i++) {
//		cout << querymax(1, i) << " " << querymin(1, i) << " " << ssum[i] << " " << sum[i] << " " << l[i] << " " << r[i] << "\n";
		if (querymax(1, i) <= sum[i] && querymin(1, i) >= sum[i]) {
			ans = max(ans, i - lst);
			lst = i;
		}
		changemax(1, XD{l[i], -ssum[i]*l[i] + sum[i]});
		changemin(1, XD{r[i], -ssum[i]*r[i] + sum[i]});
//		if (n - i == 3) {
//			for (int j = 1; j < i; j++) {
//				if (sum[i] - sum[j] < l[j] * (ssum[i] - ssum[j]) || sum[i] - sum[j] > r[j] * (ssum[i] - ssum[j])) {
//					cout << j << "[]\n";
//				}
//			}
//		}
//		cout << b[1].minn.k << " " << b[1].minn.b << " " << b[1].maxn.k << ' ' << b[1].maxn.b << " " << calc(b[1].minn, ssum[i + 1]) << " " << calc(b[1].maxn, ssum[i + 1]) << "[[]%$&^\n";
	}
	ans = max(ans, n - lst);
	cout << ans;
}
//A 题不会做 Ai=Bi 的情况,快写完了才想起来,我炸了

//尼玛这题也读错了一次,读错小子
//最开始还以为只要捞一叠出来就行,没想到原来是这个意思

详细

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 0ms
memory: 1276kb

input:

11
2708 8257
1109 5518
4522 6569
4677 5432
3328 7258
4135 4882
4762 6608
4876 4975
1210 6880
4621 83...

output:

10

result:

ok "10"

Test #2:

score: 0
Accepted
time: 0ms
memory: 1268kb

input:

11
1669 7912
4731 9074
5616 9691
993 8876
5762 9840
6012 6601
5062 6096
5985 6134
3858 7098
5997 607...

output:

9

result:

ok "9"

Subtask #2:

score: 10
Accepted

Test #3:

score: 10
Accepted
time: 0ms
memory: 1288kb

input:

91
2708 8257
5482 5488
5476 5485
5473 5492
5473 5488
5475 5491
5482 5486
5478 5486
5480 5483
5474 54...

output:

20

result:

ok "20"

Test #4:

score: 0
Accepted
time: 0ms
memory: 1284kb

input:

98
6039 8746
7387 7395
7388 7397
7390 7401
7382 7396
7388 7402
7392 7394
7388 7397
7391 7398
7389 73...

output:

14

result:

ok "14"

Subtask #3:

score: 20
Accepted

Test #5:

score: 20
Accepted
time: 2ms
memory: 1784kb

input:

3994
4439 9505
6968 6975
6971 6978
6963 6980
6966 6974
6963 6974
6963 6981
6967 6972
6968 6977
6963 ...

output:

682

result:

ok "682"

Test #6:

score: 0
Accepted
time: 2ms
memory: 1788kb

input:

3991
3415 3917
3664 3676
3656 3673
3666 3667
3666 3673
3656 3673
3657 3668
3663 3668
3657 3675
3662 ...

output:

579

result:

ok "579"

Test #7:

score: 0
Accepted
time: 1ms
memory: 1788kb

input:

3994
971 5008
2984 2994
2982 2990
2983 2997
2980 2997
2984 2991
2984 2999
2985 2995
2986 2997
2982 2...

output:

572

result:

ok "572"

Test #8:

score: 0
Accepted
time: 1ms
memory: 1788kb

input:

3995
3414 8486
5942 5953
5945 5959
5945 5956
5949 5951
5949 5955
5944 5959
5942 5959
5940 5957
5944 ...

output:

513

result:

ok "513"

Subtask #4:

score: 60
Accepted

Test #9:

score: 60
Accepted
time: 41ms
memory: 16684kb

input:

99995
1046 7816
4393 4447
4366 4514
4385 4495
4426 4507
4342 4470
4380 4479
4417 4458
4341 4516
4425...

output:

46415

result:

ok "46415"

Test #10:

score: 0
Accepted
time: 45ms
memory: 16684kb

input:

99993
7441 9162
8213 8330
8254 8337
8292 8310
8260 8332
8219 8345
8290 8379
8276 8386
8235 8398
8230...

output:

29730

result:

ok "29730"

Test #11:

score: 0
Accepted
time: 41ms
memory: 16680kb

input:

99995
3146 3809
3382 3501
3411 3555
3465 3481
3455 3508
3452 3496
3446 3476
3425 3524
3428 3572
3474...

output:

57697

result:

ok "57697"

Test #12:

score: 0
Accepted
time: 51ms
memory: 16680kb

input:

99993
2480 8481
5455 5554
5450 5543
5480 5509
5469 5493
5465 5559
5394 5552
5477 5533
5416 5508
5440...

output:

48186

result:

ok "48186"

Test #13:

score: 0
Accepted
time: 37ms
memory: 16684kb

input:

99991
4938 7534
6171 6236
6191 6246
6147 6309
6203 6297
6170 6266
6153 6326
6229 6239
6224 6317
6160...

output:

99518

result:

ok "99518"

Test #14:

score: 0
Accepted
time: 29ms
memory: 16684kb

input:

100000
0 10000
0 10000
0 10000
0 10000
0 10000
0 10000
0 10000
0 10000
0 10000
0 10000
0 10000
0 100...

output:

56

result:

ok "56"

Test #15:

score: 0
Accepted
time: 44ms
memory: 16684kb

input:

99992
3946 4746
4250 4406
4281 4399
4292 4349
4260 4410
4258 4383
4329 4350
4328 4357
4324 4422
4270...

output:

53203

result:

ok "53203"

Test #16:

score: 0
Accepted
time: 43ms
memory: 16684kb

input:

99990
6960 8101
7513 7608
7468 7573
7489 7541
7457 7582
7439 7622
7519 7567
7486 7593
7521 7539
7513...

output:

28892

result:

ok "28892"

Test #17:

score: 0
Accepted
time: 65ms
memory: 16684kb

input:

99990
4006 8561
6202 6361
6280 6355
6258 6290
6260 6351
6196 6348
6282 6297
6238 6285
6219 6334
6231...

output:

41258

result:

ok "41258"

Test #18:

score: 0
Accepted
time: 78ms
memory: 16680kb

input:

99998
4207 5524
4780 4957
4851 4925
4811 4883
4854 4906
4820 4900
4822 4877
4772 4868
4810 4888
4767...

output:

42109

result:

ok "42109"

Test #19:

score: 0
Accepted
time: 76ms
memory: 16680kb

input:

99995
2153 4894
3473 3597
3434 3570
3446 3570
3442 3585
3481 3548
3503 3596
3431 3557
3463 3532
3449...

output:

51628

result:

ok "51628"

Test #20:

score: 0
Accepted
time: 69ms
memory: 16680kb

input:

99998
1338 6867
4091 4201
4077 4183
4021 4164
4070 4196
4061 4155
4029 4192
4019 4192
4096 4126
4028...

output:

35604

result:

ok "35604"