QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #927802 | #10150. 推箱子 | rizynvu | 100 ✓ | 1107ms | 20312kb | C++14 | 1.7kb | 2025-03-07 16:18:32 | 2025-03-07 16:18:32 |
Judging History
answer
#include<bits/stdc++.h>
using ll = long long;
constexpr int maxn = 2e5 + 10;
int n;
int p[maxn]; ll a[maxn], b[maxn], t[maxn];
std::map<int, int> S; ll wl[maxn];
inline void add(int l, int r, ll wL) {
S[l] = r, wl[l] = wL;
}
inline void split(int w) {
auto [L, R] = *std::prev(S.upper_bound(w));
if (L < w) {
add(L, w - 1, wl[L]);
add(w, R, wl[L] + w - L);
}
if (w < R) {
add(w, w, wl[w]);
add(w + 1, R, wl[w] + 1);
}
}
inline void solve() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld%lld%lld", &a[i], &b[i], &t[i]), p[i] = i;
}
std::sort(p + 1, p + n + 1, [&](int x, int y) {
return t[x] < t[y];
});
S.clear();
add(0, 0, 0ll), add(n + 1, n + 1, (ll)3e9);
for (int i = 1; i <= n; i++) add(i, i, a[i]);
ll T = 0;
for (int i = 1; i <= n; i++) {
int id = p[i]; split(id);
auto it = S.find(id);
if (wl[id] < b[id]) {
int sr = id;
for (; ; ) {
auto [l, r] = *it;
ll w = b[id] + l - id;
if (wl[l] >= w) break;
assert(l != n + 1 && l != 0);
T += 1ll * (w - wl[l]) * (r - l + 1), sr = r;
S.erase(it++);
}
add(id, sr, b[id]);
} else if (wl[id] > b[id]) {
int sl = id;
for (; ; ) {
auto [l, r] = *it;
ll w = b[id] + l - id;
if (wl[l] <= w) break;
assert(l != n + 1 && l != 0);
T += 1ll * (wl[l] - w) * (r - l + 1), sl = l;
S.erase(it--);
}
add(sl, id, b[id] + sl - id);
}
if (T > t[id]) return puts("No"), void();
}
puts("Yes");
}
int main() {
int c, T; scanf("%d%d", &c, &T);
for (; T--; ) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 4
Accepted
time: 0ms
memory: 8024kb
input:
1 6 7 4 1 58 5 2 58 6 3 58 9 7 58 10 8 58 11 14 58 12 15 58 7 2 1 7922535048395476 6 3 7922535048395476 7 4 7922535048395476 8 5 7922535048395476 13 10 7922535048395476 14 11 7922535048395476 15 12 7922535048395476 6 1 4 105 2 6 105 3 9 105 10 13 105 11 14 105 12 15 105 5 1 5 67 2 6 67 8 9 67 13 10 ...
output:
Yes Yes Yes Yes No Yes
result:
ok 6 token(s): yes count is 5, no count is 1
Test #2:
score: 4
Accepted
time: 0ms
memory: 10064kb
input:
2 6 7 1 4 12 2 5 14 3 6 12 8 7 15 11 10 13 12 14 15 13 15 6 6 5 1 18 6 3 15 7 4 15 9 10 16 14 11 7 15 12 6 6 6 1 17 7 2 18 8 5 14 9 11 3 12 14 19 13 15 3 6 4 3 12 6 5 2 7 10 10 8 11 10 9 12 12 14 13 11 6 1 2 0 3 6 18 4 8 6 9 13 16 11 14 12 12 15 19 5 4 1 10 5 2 15 6 7 8 9 12 6 10 14 8
output:
Yes Yes No Yes No No
result:
ok 6 token(s): yes count is 3, no count is 3
Test #3:
score: 4
Accepted
time: 0ms
memory: 10064kb
input:
3 6 7 2 1 16 7 3 15 8 4 13 9 6 10 10 11 11 13 12 14 15 14 14 7 1 2 1 3 7 13 4 8 13 6 9 21 13 10 22 14 11 22 15 12 20 5 1 3 4 2 4 4 5 6 6 8 11 11 9 14 13 7 1 2 13 5 3 18 6 4 17 8 7 16 13 9 12 14 10 9 15 12 11 6 2 5 8 3 6 10 4 7 13 9 11 13 12 13 11 14 15 14 5 3 6 6 4 7 4 9 12 12 11 13 9 15 14 13
output:
Yes No Yes Yes No Yes
result:
ok 6 token(s): yes count is 4, no count is 2
Test #4:
score: 4
Accepted
time: 0ms
memory: 10064kb
input:
4 6 199 37 18 65874 50 20 65874 52 42 65874 64 60 65874 72 70 65874 85 82 65874 93 91 65874 109 92 65874 111 97 65874 131 102 65874 148 130 65874 164 138 65874 199 167 65874 217 203 65874 243 214 65874 247 224 65874 271 229 65874 308 233 65874 309 246 65874 318 283 65874 334 331 65874 347 333 65874 ...
output:
No No No No Yes Yes
result:
ok 6 token(s): yes count is 2, no count is 4
Test #5:
score: 4
Accepted
time: 1ms
memory: 8016kb
input:
5 6 199 29 36 369 64 70 1143 71 74 1229 80 94 519 97 102 309 105 142 959 144 160 1243 161 170 1397 184 192 494 198 210 779 212 220 703 222 236 120 239 240 1064 254 264 593 266 271 920 277 281 988 289 292 1319 306 312 664 327 333 1265 336 347 457 357 360 1214 370 388 679 389 396 633 401 411 578 420 4...
output:
No Yes Yes Yes Yes No
result:
ok 6 token(s): yes count is 4, no count is 2
Test #6:
score: 4
Accepted
time: 1ms
memory: 8020kb
input:
6 6 199 45 22 74188 49 33 74205 51 73 58578 71 89 63891 78 92 67804 98 118 63860 99 125 64921 120 128 49873 138 140 40221 142 157 52577 147 184 39214 151 199 55174 167 208 60545 192 213 63389 215 216 64903 235 275 67610 239 281 68856 245 294 70226 247 312 71083 308 339 73698 318 344 74817 336 348 75...
output:
Yes Yes No Yes No No
result:
ok 6 token(s): yes count is 3, no count is 3
Test #7:
score: 4
Accepted
time: 0ms
memory: 10064kb
input:
7 6 198 157 1 90695 179 3 90463 184 5 89928 187 22 89308 191 32 87453 194 36 87435 205 38 85944 207 40 85557 213 59 85314 220 65 84891 228 68 84875 233 71 83145 234 78 82323 235 81 78303 237 92 76908 261 102 76525 275 107 76402 279 112 76524 284 124 63459 288 142 63250 315 156 59959 371 320 65555 37...
output:
Yes No No Yes No Yes
result:
ok 6 token(s): yes count is 3, no count is 3
Test #8:
score: 4
Accepted
time: 10ms
memory: 10188kb
input:
8 6 2998 703476 350568 361034127833 725807 436492 361034127833 1231986 1230439 361034127833 1706679 1235832 361034127833 1849695 1427192 361034127833 1862833 1437577 361034127833 1975829 3186583 361034127833 2086881 3335536 361034127833 2390103 3385039 361034127833 2499416 3604747 361034127833 27327...
output:
No Yes Yes Yes No No
result:
ok 6 token(s): yes count is 3, no count is 3
Test #9:
score: 4
Accepted
time: 7ms
memory: 10192kb
input:
9 6 3000 182672 204002 145628966 233619 264606 66203026 328887 573420 456314943 631179 797510 34453437 1294808 1380985 4692244 1391318 1530506 431577632 1608324 1729541 85569640 1837920 1994485 75594999 2072112 2087294 104826376 2285152 2336929 145990083 2393282 2673930 284568560 2783869 2792779 860...
output:
No No Yes No No No
result:
ok 6 token(s): yes count is 1, no count is 5
Test #10:
score: 4
Accepted
time: 8ms
memory: 10064kb
input:
10 6 3000 2222227 31532 279636770304 2349942 134163 354400286918 2560041 527419 321478195282 3295593 596563 362129656617 3869141 612649 374151982522 3909494 845994 219496747652 4164077 1014016 347814863593 4434642 1048014 277805151037 4819441 1099088 333450514907 5703758 1633041 328059389030 6192622...
output:
No Yes No Yes Yes No
result:
ok 6 token(s): yes count is 3, no count is 3
Test #11:
score: 4
Accepted
time: 8ms
memory: 10184kb
input:
11 6 2999 220527 342273 250754055236 254255 471191 396588863964 297822 814315 450935385357 733075 980291 457899271625 1054047 185178250 1311693556589166 1161026 185790557 563819064114 1241182 186158539 563634434603 1325885 186411046 563613864771 1385875 186679798 563263522481 1390136 186974536 56307...
output:
No Yes Yes Yes No No
result:
ok 6 token(s): yes count is 3, no count is 3
Test #12:
score: 4
Accepted
time: 289ms
memory: 14164kb
input:
12 6 79998 249167 1 19964147940 249174 5 19964147940 249182 8 19964147940 249191 9 19964147940 249192 13 19964147940 249195 14 19964147940 249200 18 19964147940 249202 19 19964147940 249211 27 19964147940 249213 29 19964147940 249214 33 19964147940 249215 34 19964147940 249218 36 19964147940 249219 ...
output:
Yes Yes No Yes Yes No
result:
ok 6 token(s): yes count is 4, no count is 2
Test #13:
score: 4
Accepted
time: 322ms
memory: 14156kb
input:
13 6 79998 2 3 85085 5 7 110934 8 10 76447 19 21 113382 22 34 116328 43 44 92641 63 69 82679 79 82 150338 89 93 83248 94 106 206262 107 110 103397 116 117 38256 119 133 117971 138 139 15052 142 146 112276 148 150 178878 152 161 224257 172 173 23098 175 179 98155 180 183 173659 184 186 244587 188 190...
output:
Yes No Yes Yes Yes No
result:
ok 6 token(s): yes count is 4, no count is 2
Test #14:
score: 4
Accepted
time: 291ms
memory: 12592kb
input:
14 6 80000 1 3 4988939908 2 5 4709983247 6 13 4269997574 10 14 4464798775 11 16 4891136602 12 19 5008095418 20 32 4844785468 21 35 4841690783 25 36 4839602763 26 37 4583024133 29 38 3551461328 39 40 5010625553 42 52 4980297573 50 56 4994880499 60 62 4978544842 63 77 3373729353 68 78 4298210945 69 79...
output:
No Yes Yes Yes Yes Yes
result:
ok 6 token(s): yes count is 5, no count is 1
Test #15:
score: 4
Accepted
time: 252ms
memory: 14416kb
input:
15 6 79999 1 249866 13200183685 4 249868 13200263686 7 249869 13200263689 17 249879 13201115618 20 249882 13201143633 22 249884 13201223628 25 249886 13201303620 37 249888 13201383610 38 249890 13201463603 41 249893 13201623593 43 249894 13201623594 46 249895 13201670636 47 249897 13201703577 48 249...
output:
Yes Yes No Yes Yes Yes
result:
ok 6 token(s): yes count is 5, no count is 1
Test #16:
score: 4
Accepted
time: 314ms
memory: 12884kb
input:
16 6 79999 249703 1 20024824567 249705 3 20024824570 249707 5 20024824558 249709 9 20024824556 249711 13 20024824540 249718 14 20024824534 249724 18 20024824521 249726 21 20024824502 249730 29 20024824452 249732 30 20024824446 249735 35 20024824407 249736 36 20024824406 249740 38 20024824396 249742 ...
output:
Yes Yes No Yes Yes Yes
result:
ok 6 token(s): yes count is 5, no count is 1
Test #17:
score: 4
Accepted
time: 273ms
memory: 12748kb
input:
17 6 79998 250288 6 19961268433 250289 7 19961268436 250290 11 19961268423 250293 13 19961268424 250295 14 19961268414 250303 16 19961268410 250306 17 19961268420 250308 20 19961268396 250314 32 19961268320 250315 35 19961268289 250319 36 19961268289 250321 39 19961268271 250323 41 19961268261 25033...
output:
Yes No Yes Yes No Yes
result:
ok 6 token(s): yes count is 4, no count is 2
Test #18:
score: 4
Accepted
time: 283ms
memory: 12880kb
input:
18 6 79998 17 1 4984837833 21 8 4663850012 22 12 4860300511 23 24 5000863386 28 26 5042057946 38 32 4767031476 42 33 3957006549 46 36 4679775591 53 43 3697383560 58 60 3335484657 61 67 3329623957 64 70 3533763558 88 78 4856080032 94 79 4598840642 96 87 5103578312 97 89 4406500840 98 93 3672001950 10...
output:
No Yes Yes Yes Yes No
result:
ok 6 token(s): yes count is 4, no count is 2
Test #19:
score: 4
Accepted
time: 1107ms
memory: 20312kb
input:
19 6 199998 4752 8452 119973858 8641 9204 241564106 13059 20180 265705199 22139 22257 371269578 25275 28894 237538945 29846 29862 474164808 31329 31643 20840351 32051 35475 481710652 38644 40274 374391929 42082 42339 55354676 48966 51694 94077254 54309 57689 469656627 59151 59684 2634589 60197 60316...
output:
No No No Yes Yes Yes
result:
ok 6 token(s): yes count is 3, no count is 3
Test #20:
score: 4
Accepted
time: 954ms
memory: 20180kb
input:
20 6 199998 26 3181 71497185 4034 4169 253881356 5588 10348 273394692 14533 14909 484599741 16739 16820 391395579 17015 19115 489829084 20536 20656 308020799 29649 30545 223163784 34872 34964 385515859 38482 39763 346742942 41178 41505 225380750 43384 44826 444505766 45775 46237 378962392 48122 4923...
output:
No Yes Yes No Yes No
result:
ok 6 token(s): yes count is 3, no count is 3
Test #21:
score: 4
Accepted
time: 920ms
memory: 20176kb
input:
21 6 199999 385 499729204 49973268223870 5671 499733521 49975598588773 8473 499742695 49975816958706 8607 499744568 49976191351207 10008 499754631 49978226417477 20344 499758687 49979057183863 23375 499759373 49979151671736 25038 499761854 49980095812335 25212 499764540 49980267024910 27314 49976499...
output:
Yes No Yes Yes Yes Yes
result:
ok 6 token(s): yes count is 5, no count is 1
Test #22:
score: 4
Accepted
time: 916ms
memory: 20308kb
input:
22 6 199999 1559 6500 21276104256382 3535 8380 24379101146289 6626 17675 22430167309624 8624 21116 24544729879990 22708 23269 22196297813107 26167 27130 13393699902230 27263 27486 24795781452827 29899 30162 23661729961219 30457 31557 23242086684450 33192 34535 24359965896122 33666 47228 248722127534...
output:
Yes Yes No Yes Yes Yes
result:
ok 6 token(s): yes count is 5, no count is 1
Test #23:
score: 4
Accepted
time: 886ms
memory: 20180kb
input:
23 6 200000 500779345 5217 99914602292023 500786016 10755 99914602286451 500786376 14331 99914602279326 500790111 16701 99914602275849 500795539 19071 99914602262716 500796086 24482 99914602235714 500800488 25559 99914602229212 500800958 26552 99914602222302 500804392 29654 99914602202540 500804762 ...
output:
Yes Yes Yes Yes Yes No
result:
ok 6 token(s): yes count is 5, no count is 1
Test #24:
score: 4
Accepted
time: 796ms
memory: 20304kb
input:
24 6 199998 5506 499553171 50000813841622 7523 499555351 50001264432119 12319 499555718 50002227729732 14435 499562243 50002627600951 20585 499563300 50002838794654 24128 499563420 50003086339716 25184 499565069 50003192180625 26272 499567370 50003652159926 30412 499568816 50003941145458 30759 49956...
output:
No No Yes No No Yes
result:
ok 6 token(s): yes count is 2, no count is 4
Test #25:
score: 4
Accepted
time: 858ms
memory: 20304kb
input:
25 6 199999 1835 7026 20930046212798 1968 9460 19017482627921 14954 28845 21795564477058 31838 30996 19632139451212 39876 37417 25377149702336 49265 42233 17475858301617 49787 7332957 17790307884540 55521 7333598 24311981507252 57406 7334415 25180134103886 57427 7337225 16857512321347 57533 7340842 ...
output:
No Yes Yes Yes No Yes
result:
ok 6 token(s): yes count is 4, no count is 2
Extra Test:
score: 0
Extra Test Passed