QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#609284#9427. Collect the CoinsYzm007AC ✓227ms19600kbC++141.7kb2024-10-04 11:46:382024-10-04 11:46:39

Judging History

你现在查看的是测评时间为 2024-10-04 11:46:39 的历史记录

  • [2024-11-06 16:01:59]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:226ms
  • 内存:19572kb
  • [2024-11-06 15:56:27]
  • hack成功,自动添加数据
  • (/hack/1139)
  • [2024-10-04 11:46:39]
  • 评测
  • 测评结果:100
  • 用时:227ms
  • 内存:19600kb
  • [2024-10-04 11:46:38]
  • 提交

answer

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=1e6+10;
const ll INF=1e9;
int t,n;
P a[N];
bool can(ll p,ll l,ll r,ll d){
    return l-d<=p && p<=r+d;
}
bool ok(ll v){
    int p=1;
    ll l=1,r=INF;
    rep(i,2,n){
        ll T=a[i].fi-a[p].fi,d=T*v;
        bool x=can(a[i].se,a[p].se,a[p].se,d),y=can(a[i].se,l,r,d);
        if(x && y){
            l=min(l-d,a[p].se-d);
            r=max(r+d,a[p].se+d);
        }
        else if(x){
            l=l-d;
            r=r+d;
        }
        else if(y){
            l=a[p].se-d;
            r=a[p].se+d;
        }
        else{
            return 0;
        }
        p=i;
        l=max(1ll,l);
        r=min(INF,r);
    }
    return 1;
}
ll sol(){
    sci(n);
    rep(i,1,n){
        scanf("%lld%lld",&a[i].fi,&a[i].se);
    }
    ll l=0,r=INF;
    while(l<=r){
        ll mid=(l+r)/2;
        if(ok(mid))r=mid-1;
        else l=mid+1;
    }
    if(l>INF)return -1;
    return l;
}
int main(){
    sci(t);
    while(t--){
        ptlle(sol());
    }
    return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3788kb

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: 19ms
memory: 3948kb

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: 227ms
memory: 19548kb

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: 145ms
memory: 19412kb

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: 163ms
memory: 19552kb

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: 15ms
memory: 4092kb

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: 189ms
memory: 19552kb

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: 147ms
memory: 19596kb

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: 177ms
memory: 19472kb

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: 149ms
memory: 19596kb

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: 161ms
memory: 19536kb

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: 190ms
memory: 19484kb

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: 14ms
memory: 4152kb

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: 145ms
memory: 19552kb

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: 139ms
memory: 19460kb

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: 160ms
memory: 19476kb

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: 144ms
memory: 19492kb

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: 149ms
memory: 19552kb

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: 151ms
memory: 19536kb

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: 149ms
memory: 19592kb

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: 176ms
memory: 19492kb

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: 151ms
memory: 19552kb

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: 152ms
memory: 19568kb

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: 142ms
memory: 19600kb

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