ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#203931 | #555. 积木 | tkswls | 100 | 625ms | 16684kb | C++11 | 3.1kb | 2024-03-26 11:36:57 | 2024-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 的情况,快写完了才想起来,我炸了
//尼玛这题也读错了一次,读错小子
//最开始还以为只要捞一叠出来就行,没想到原来是这个意思
Details
小提示:点击横条可展开更详细的信息
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"