QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#608111 | #9427. Collect the Coins | 2497201210 | TL | 635ms | 66112kb | C++20 | 1.7kb | 2024-10-03 18:34:44 | 2024-11-06 16:01:45 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=1e6+10;
const int P=1e9+7;
pair<int,vector<int>>md[N];
int idx=0;
bool check(int x) {
int l=-1e10;int r=1e10;
int d;
if(md[1].second.size()==1){
d=md[1].second[0];
}
else {
d=md[1].second[0];
l=r=md[1].second[1];
}
for(int i=2;i<=idx;i++){
int cha=md[i].first-md[i-1].first;
cha=cha*x;
l-=cha;r+=cha;
if(md[i].second.size()==2){
int pos1=md[i].second[0];int pos2=md[i].second[1];
if(pos1>=d-cha&&pos1<=d+cha&&pos2>=l&&pos2<=r){
d=pos1;
l=r=pos2;
}
else if(pos2>=d-cha&&pos2<=d+cha&&pos1>=l&&pos1<=r){
d=pos1;
l=r=pos2;
}
else{
return 0;
}
}
else{
int pos=md[i].second[0];
if(pos>=l&&pos<=r&&pos>=d-cha&&pos<=d+cha){
l=min(l,d-cha);
r=max(r,d+cha);d=pos;
}
else{
if(pos>=l&&pos<=r){
l=d-cha;
r=d+cha;
d=pos;
}
else if(pos>=d-cha&&pos<=d+cha){
d=pos;
}
else{
return 0;
}
}
}
}
return 1;
}
inline void solve() {
int n;
cin>>n;
bool f=1;idx=0;
for(int i=1; i<=n; i++) {
int a,b;
cin>>a>>b;
if(idx==0||md[idx].first!=a){
md[++idx].first=a;
md[idx].second.resize(0);
md[idx].second.push_back(b);
}
else{
md[idx].second.push_back(b);
}
if(md[idx].second.size()>2)f=0;
}
if(f) {
int l=0;
int r=1e9+100;
while(l<r) {
int mid=l+r>>1;
if(check(mid))r=mid;
else l=mid+1;
}
cout<<l<<endl;
} else {
cout<<-1<<endl;
}
}
signed main() {
cin.tie(0);
cout.tie(0);
int t;
t=1;
cin>>t;
while(t--) {
solve();
}
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3524kb
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: 44ms
memory: 4304kb
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: 494ms
memory: 46536kb
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: 470ms
memory: 63404kb
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: 570ms
memory: 66088kb
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: 44ms
memory: 4228kb
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: 502ms
memory: 66024kb
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: 504ms
memory: 66104kb
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: 588ms
memory: 66024kb
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: 466ms
memory: 64368kb
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: 511ms
memory: 63720kb
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: 591ms
memory: 63364kb
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: 42ms
memory: 3860kb
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: 403ms
memory: 36588kb
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: 456ms
memory: 35888kb
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: 515ms
memory: 36376kb
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: 481ms
memory: 66016kb
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: 635ms
memory: 66112kb
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: -100
Time Limit Exceeded
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