QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#624643 | #9427. Collect the Coins | ucup-team2000 | AC ✓ | 835ms | 62372kb | C++23 | 2.6kb | 2024-10-09 16:18:45 | 2024-11-06 16:03:03 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e6 + 100;
ll n;
pair<ll, ll> vec[maxn];
set<pair<ll, ll>> all;
unordered_set<ll> all_pos;
ll V;
bool valid(ll i, ll j) {
auto [t1, p1] = vec[i];
auto [t2, p2] = vec[j];
return abs(p1 - p2) <= abs(t1 - t2) * V;
}
void insert(ll pos) {
auto [t, p] = vec[pos];
// insert (p - tV, -p-tV)
// ...
auto x = p - t * V;
auto y = -p - t * V;
bool flag = true;
auto rit = all.lower_bound({x, y});
if (rit == all.end())
flag = true;
else {
auto [tx, ty] = *rit;
if (ty < y)
flag = true;
else
flag = false;
}
if (flag) {
auto it = rit;
while (it != all.begin()) {
auto pit = prev(it, 1);
auto [tx, ty] = *pit;
if (ty <= y)
all.erase(pit);
else
break;
}
all.insert({x, y});
}
}
bool check() {
static bool dp[maxn];
std::fill(dp, dp + n + 1, 0);
all.clear();
for (int i = 2; i < n; i++) {
if (!valid(i - 1, i)) break;
dp[i + 1] = true;
}
// check st = 2, i = 3?
dp[2] = true;
for (ll i = 3; i <= n; i++) {
if (!valid(i - 2, i - 1)) {
all.clear();
}
// cout << "addr2" << endl;
if (dp[i - 1]) insert(i - 2);
// j-1
auto [qt, qp] = vec[i];
auto qx = qp - qt * V;
auto qy = -qp - qt * V;
auto it = all.lower_bound({qx, qy});
if (it != all.end()) {
auto [tx, ty] = *it;
if (ty >= qy) dp[i] = true;
}
}
for (int temp = n; temp >= 1; temp--) {
if (temp < n and !valid(temp, temp + 1)) break;
if (dp[temp]) return true;
}
return false;
};
void solve() {
cin >> n;
for (ll i = 1; i <= n; i++) {
cin >> vec[i].first >> vec[i].second;
}
all_pos.clear();
for (ll i = 1; i <= n; i++) {
all_pos.insert(vec[i].second);
}
if (all_pos.size() <= 2) {
cout << 0 << '\n';
return;
}
ll L = 1, R = 1e9 + 100;
while (L < R) {
ll mid = (L + R) / 2;
V = mid;
if (check())
R = mid;
else
L = mid + 1;
}
if (L > 1e9) L = -1;
cout << L << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5640kb
input:
3 5 1 1 3 7 3 4 4 3 5 10 1 10 100 3 10 100 10 1000 10 10000
output:
2 0 -1
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 35ms
memory: 8180kb
input:
1135 2 6 5 8 8 8 2 9 2 10 4 4 5 3 6 2 6 8 8 2 8 7 1 9 1 6 4 6 6 1 6 2 9 10 10 1 10 7 5 1 6 2 5 6 7 8 6 10 3 8 1 10 5 4 5 7 6 1 6 6 8 4 9 1 9 4 8 1 1 1 3 2 9 3 3 5 9 6 10 9 7 10 7 3 5 8 6 6 10 6 7 2 9 4 7 5 10 6 3 6 7 8 9 10 1 6 1 4 2 8 5 9 7 10 9 1 10 5 9 2 7 4 5 5 9 6 10 7 4 9 4 9 9 10 3 10 7 1 3 1...
output:
0 3 0 3 1 3 6 0 3 2 2 0 2 5 0 1 5 1 2 0 0 0 1 4 2 0 2 1 3 0 3 2 3 2 5 3 1 1 0 1 1 1 0 2 0 1 0 1 0 2 1 0 2 3 4 4 1 1 1 0 1 3 0 1 4 4 3 0 0 2 2 6 4 2 1 0 0 1 0 2 1 2 0 1 1 3 0 0 1 2 0 3 0 2 2 2 1 0 0 0 5 1 2 0 6 1 1 1 2 2 2 0 3 1 4 3 6 0 8 1 1 3 0 2 2 4 1 1 0 0 0 7 2 2 1 0 0 3 1 2 1 1 2 5 3 0 3 3 3 5 ...
result:
ok 1135 lines
Test #3:
score: 0
Accepted
time: 782ms
memory: 45104kb
input:
1 1000000 2 57841 2 357142 3 496329 3 545446 4 503408 4 590762 5 78281 6 196926 6 349414 7 200245 8 953412 11 616898 12 592065 13 945945 15 20908 15 852722 16 221184 16 401521 17 884478 18 186072 18 931445 19 833560 20 314177 21 138453 21 731965 22 172104 23 595921 25 372617 27 545759 28 977029 30 4...
output:
994024
result:
ok single line: '994024'
Test #4:
score: 0
Accepted
time: 412ms
memory: 60720kb
input:
1 1000000 6 1991827 13 8125243 19 22493 24 4282711 28 356362 39 765152 41 6737899 44 8549464 57 4530192 64 7201376 67 6695629 70 3830504 70 6658581 71 4591382 71 8349070 75 2107828 76 4073563 81 2712838 92 1391185 95 4663781 102 5986957 113 8423636 118 7826607 122 1171556 122 3118750 160 938066 162 ...
output:
9609125
result:
ok single line: '9609125'
Test #5:
score: 0
Accepted
time: 408ms
memory: 62172kb
input:
1 1000000 108 565196036 597 561009880 1007 831705109 2597 55966094 2869 765993518 3025 202191673 3283 237167825 3410 829643653 4879 960747182 7284 679152790 8765 64201585 8899 97619554 9320 713144607 9519 991746776 9913 346063307 11161 970513525 11256 975123550 12073 778562963 14286 206857559 15803 ...
output:
268764694
result:
ok single line: '268764694'
Test #6:
score: 0
Accepted
time: 50ms
memory: 4048kb
input:
1135 9 1 7 3 7 4 10 5 2 6 8 7 10 8 3 9 10 10 4 9 1 4 3 2 4 1 5 3 5 7 7 2 8 4 10 7 10 10 5 3 10 4 4 7 3 8 8 9 7 8 4 1 4 4 5 5 6 4 8 3 8 4 9 2 9 4 3 1 4 5 3 10 9 7 2 6 3 4 4 2 6 3 6 9 8 3 8 7 7 1 5 3 6 4 8 4 9 5 10 8 4 8 10 1 8 6 9 1 6 2 6 3 9 5 9 6 7 6 9 8 1 9 4 10 4 5 3 9 4 3 4 6 6 4 8 5 7 1 1 2 1 3...
output:
3 2 1 1 1 2 2 0 3 3 4 0 4 1 3 2 0 0 0 3 2 6 3 0 1 0 4 0 3 0 2 0 3 0 0 1 4 0 1 2 4 0 2 1 1 1 2 8 1 1 1 1 1 5 0 1 0 3 0 3 2 2 3 2 5 0 0 2 6 4 3 2 2 1 2 0 0 4 5 0 6 5 0 4 3 5 4 1 3 0 0 2 0 8 2 1 1 2 1 3 1 1 4 0 5 0 4 0 1 6 0 7 1 1 0 3 2 1 5 1 3 1 1 8 3 0 2 1 1 0 0 1 1 1 0 6 1 1 1 1 0 0 1 3 1 4 0 2 0 1 ...
result:
ok 1135 lines
Test #7:
score: 0
Accepted
time: 539ms
memory: 45020kb
input:
1 1000000 1 421151 2 313604 3 982622 4 993745 5 997253 6 859839 7 835793 8 324554 9 553026 10 218950 11 672201 12 373214 13 147841 14 445973 15 807912 16 753995 17 564224 18 662086 19 862430 20 378806 21 591406 22 415543 23 490080 24 184083 25 287323 26 578004 27 302543 28 302371 29 689597 30 538475...
output:
492642
result:
ok single line: '492642'
Test #8:
score: 0
Accepted
time: 418ms
memory: 60948kb
input:
1 1000000 4 5761079 27 9913703 31 3480982 33 8607438 37 3321663 64 3998110 72 4273261 78 7438482 84 8988669 96 920933 101 9309679 106 2230436 118 8605436 123 104422 129 7742745 131 4597839 139 9509656 142 3293909 159 9386630 176 9018043 188 3538661 207 9103530 233 2796496 239 7390510 246 2350961 249...
output:
4801594
result:
ok single line: '4801594'
Test #9:
score: 0
Accepted
time: 442ms
memory: 62192kb
input:
1 1000000 1659 745509192 1793 453656007 2417 245865714 3481 181708105 4181 423236911 5279 477367945 7195 966897525 9086 169940320 12642 77818181 14303 26150912 15915 448404964 16486 168882999 16531 105802492 16723 521426994 16754 508715351 19350 563835961 20119 410674400 20775 157959337 20870 320155...
output:
257246803
result:
ok single line: '257246803'
Test #10:
score: 0
Accepted
time: 374ms
memory: 44948kb
input:
1 1000000 1 199948 2 400091 2 463093 3 30523 4 771947 6 320897 7 104702 8 993244 9 926737 10 794612 11 210817 12 351420 13 495204 14 86010 16 589773 17 940494 18 467002 19 785066 20 724000 21 843646 22 47780 23 44610 24 494920 25 717543 27 869625 27 888906 28 972386 29 138651 30 73442 31 229124 32 4...
output:
983172
result:
ok single line: '983172'
Test #11:
score: 0
Accepted
time: 463ms
memory: 60924kb
input:
1 1000000 8 4343641 20 9188668 27 7784999 36 567704 71 225957 104 1690417 111 6719613 130 3931557 131 4091107 138 6733754 140 694514 143 5699446 164 8271151 190 5161164 204 6604398 219 7818039 225 103011 225 1033586 229 5290991 258 6252181 268 7412984 269 1107497 270 5043326 282 5968288 303 893538 3...
output:
9374697
result:
ok single line: '9374697'
Test #12:
score: 0
Accepted
time: 495ms
memory: 62176kb
input:
1 1000000 339 331918409 1828 806301739 4285 288684076 5821 210020913 6987 489751813 8084 346009704 9692 770088627 10407 404154547 10866 421926603 11062 935900735 11722 724947155 13636 832546152 16251 197187715 16251 291560397 17148 385272967 18475 77755669 19621 568102456 21145 20338367 21638 135488...
output:
907611400
result:
ok single line: '907611400'
Test #13:
score: 0
Accepted
time: 71ms
memory: 6120kb
input:
1135 10 1 3 1 7 2 3 2 5 4 7 4 8 6 1 6 4 7 5 7 8 8 1 4 2 2 2 3 3 5 3 10 6 8 9 1 9 4 1 10 7 1 2 5 6 1 6 1 9 5 2 5 9 8 1 8 4 6 5 8 5 9 6 5 6 10 8 3 8 9 9 1 5 1 6 4 9 5 6 5 7 7 2 7 10 10 2 10 3 3 6 9 10 5 10 8 3 4 6 4 7 7 10 1 8 6 7 1 2 2 3 2 10 3 4 3 6 5 4 5 9 3 2 1 2 9 7 7 8 6 2 6 8 7 6 7 7 8 2 8 3 10...
output:
4 7 0 0 2 3 3 1 1 0 4 1 4 1 0 1 0 7 1 2 1 3 3 1 4 4 0 0 2 0 2 5 0 3 1 3 2 4 0 0 4 2 0 6 5 2 1 3 0 1 2 0 2 2 2 2 0 1 4 5 0 6 5 5 0 0 2 0 2 3 1 5 5 4 3 6 0 2 3 7 1 0 0 0 1 1 4 2 5 4 0 0 3 3 0 0 1 0 3 1 2 5 3 2 3 5 0 1 3 7 4 3 3 0 2 0 0 1 1 3 3 1 0 0 3 1 0 0 6 3 6 7 1 0 0 4 4 0 0 1 4 2 3 2 1 6 0 0 2 0 ...
result:
ok 1135 lines
Test #14:
score: 0
Accepted
time: 833ms
memory: 44952kb
input:
1 1000000 2 77901 2 299883 4 428639 4 813168 5 100173 5 782917 7 40384 7 449788 11 236799 11 975047 12 459959 12 627756 14 268070 14 838229 15 42307 15 750817 18 429714 18 542540 20 396104 20 555946 24 382023 24 670885 25 123347 25 160290 26 338330 26 462536 29 78983 29 370000 32 431681 32 899225 33...
output:
993613
result:
ok single line: '993613'
Test #15:
score: 0
Accepted
time: 824ms
memory: 61000kb
input:
1 1000000 4 3326080 4 9907237 39 453090 39 7480697 52 2672608 52 7499680 78 1255223 78 1706176 117 135598 117 161705 131 2847430 131 9067040 201 2370848 201 4954617 256 832631 256 4772412 265 2646914 265 9939501 291 995828 291 7583564 311 4996097 311 8685066 334 1025837 334 8498081 338 2244726 338 2...
output:
9776177
result:
ok single line: '9776177'
Test #16:
score: 0
Accepted
time: 824ms
memory: 62232kb
input:
1 1000000 1387 627417959 1387 938885698 2331 35605535 2331 388781199 2813 377765380 2813 717077893 11097 80601983 11097 601468694 18924 26066416 18924 371804579 21959 646680704 21959 676102593 27236 566499457 27236 811388411 30230 462184409 30230 972254978 30814 68498987 30814 655963890 33826 734512...
output:
804824864
result:
ok single line: '804824864'
Test #17:
score: 0
Accepted
time: 342ms
memory: 44996kb
input:
1 1000000 1 629518 2 558549 3 383006 4 699159 5 984135 6 611950 7 799380 8 832403 9 433826 10 32632 11 47592 12 326209 13 642377 14 571080 15 323890 16 516728 17 213474 18 184305 19 671257 20 790199 21 869443 22 2422 23 891767 24 970860 25 378958 26 423947 27 591026 28 924544 29 461837 30 766426 31 ...
output:
953927
result:
ok single line: '953927'
Test #18:
score: 0
Accepted
time: 402ms
memory: 60856kb
input:
1 1000000 1 2453219 5 7814367 16 6026787 36 3033808 44 2359233 58 5665018 71 2603810 82 206926 84 179910 87 7812418 90 2144755 91 6521845 99 3620108 103 7674842 107 9537913 122 999505 123 1633867 135 3788282 151 9382734 161 996636 184 2564772 196 7480123 211 433598 225 1033075 232 3331142 237 487546...
output:
7974809
result:
ok single line: '7974809'
Test #19:
score: 0
Accepted
time: 404ms
memory: 62192kb
input:
1 1000000 1792 157427572 2445 81759698 3012 507330494 4313 706991734 4587 974169736 4676 666835954 4840 292019582 5392 810147227 5419 942861921 6835 573293913 6953 577978485 8218 455854676 8754 581632453 9288 889057541 10396 668313073 11446 595224977 12789 977427415 13012 77119835 13083 565585658 13...
output:
230091421
result:
ok single line: '230091421'
Test #20:
score: 0
Accepted
time: 835ms
memory: 38816kb
input:
1 999999 1 136925 1 161459 2 313627 2 320466 3 115332 3 437977 4 145504 4 463768 5 12663 5 257195 6 241054 6 405068 7 287300 7 423653 8 302327 8 416337 9 132886 9 280960 10 251656 10 420188 11 85941 11 484618 12 113894 12 157039 13 153213 13 411406 14 198314 14 277990 15 13759 15 108506 16 140009 16...
output:
495373
result:
ok single line: '495373'
Test #21:
score: 0
Accepted
time: 545ms
memory: 44924kb
input:
1 1000000 1 920085 2 679800 3 354411 4 604774 5 513080 6 78813 7 437813 8 52179 9 584742 10 544984 11 549062 12 548084 13 994858 14 632184 15 744175 16 986870 17 189703 18 44963 19 884564 20 715328 21 412696 22 561321 23 884898 24 810307 25 841470 26 3006 27 149403 28 247611 29 418611 30 224205 31 6...
output:
492816
result:
ok single line: '492816'
Test #22:
score: 0
Accepted
time: 335ms
memory: 45152kb
input:
1 1000000 1 401094 2 61773 3 958457 4 338430 5 274850 6 304145 7 678625 8 769677 9 947920 10 86853 11 492710 12 13994 13 718757 14 947397 15 695083 16 749975 17 585381 18 866063 19 500898 20 270430 21 919034 22 382247 23 826137 24 491368 25 320038 26 466770 27 287551 28 968193 29 927970 30 767712 31...
output:
889532765
result:
ok single line: '889532765'
Test #23:
score: 0
Accepted
time: 360ms
memory: 46832kb
input:
1 1000000 1 32137 2 121338 3 237693 4 480172335 4 579589581 5 494444 6 352026 7 666827 8 575582 9 157762 10 481367 11 362684 12 755591 13 387357 14 958444 15 186816 16 752082 17 45589 18 883533 19 595916 20 871738 21 967317 22 777428 23 581938 24 759792 25 273838 26 332489 27 574249 28 41898 29 3325...
output:
995404088
result:
ok single line: '995404088'
Test #24:
score: 0
Accepted
time: 705ms
memory: 62372kb
input:
1 1000000 2 288580820 2 663555163 3 26381652 3 181137097 4 74949959 4 737552704 8 217381500 8 653648155 16 335086067 16 380167296 17 388934831 17 826543591 18 483615861 18 945408385 19 250445258 19 277334791 20 61081324 20 75226646 22 247710165 22 999337344 24 550258386 24 601563613 25 431754165 25 ...
output:
993006109
result:
ok single line: '993006109'
Extra Test:
score: 0
Extra Test Passed