QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#605328#6401. Classic: N Real DNA Potslqh2024#TL 305ms4696kbC++171.9kb2024-10-02 16:43:502024-10-02 16:43:53

Judging History

你现在查看的是最新测评结果

  • [2024-10-02 16:43:53]
  • 评测
  • 测评结果:TL
  • 用时:305ms
  • 内存:4696kb
  • [2024-10-02 16:43:50]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define int long long
using i64 = long long;
mt19937_64 rd(time(0));
template <class K, class C = less<>> using paring_heap = __gnu_pbds::priority_queue<K, C>;
template <class K> using rb_tree = tree<K, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T, class ... A> void debug(const T & t, const A & ... a) { cerr << "[" << t, ((cerr << ", " << a), ...), cerr << "]\n"; }
const i64 mod = [](bool n) { return n ? 998244353 : 1e9 + 7; } (1);

void QAQ() {
    int n, v;
    cin >> n >> v;

    vector<array<int, 2>> a(n + 1);

    for (int i = 1; i <= n; i++) {
        cin >> a[i][0] >> a[i][1];
    }

    double l = -2e9, r = 2e9;

    auto chk = [&](double k) {
        int res = 1;
        map<double, int> q;
        for (int i = 1; i <= n; i++) {
            double t = a[i][1] - k * a[i][0];
            auto it = q.upper_bound(t);
            if (it != q.begin()) {
                it = prev(it);
                int now = it -> second + 1;
                res = max(res, now);
                it = q.lower_bound(t);
                while (it != q.end() && it -> second <= now) {
                    it = q.erase(it);
                }
                q.insert({a[i][1] - k * a[i][0], now});
            } else {
                q.insert({a[i][1] - k * a[i][0], 1});
            }
        }
        return res >= v;
    };

    for (int i = 0; i < 200; i++) {
        auto mid = (l + r) / 2;

        if (chk(mid)) {
            l = mid;
        } else {
            r = mid;
        }
    }

    cout << l << "\n";
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    for (cout << fixed << setprecision(12); t--; QAQ());
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3776kb

input:

4 3
1 2
2 4
3 3
4 1

output:

-1.000000000000

result:

ok found '-1.0000000', expected '-1.0000000', error '-0.0000000'

Test #2:

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

input:

2 2
1 1
5 3

output:

0.500000000000

result:

ok found '0.5000000', expected '0.5000000', error '0.0000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3816kb

input:

2 2
222640995 547139825
489207317 725361095

output:

0.668581344646

result:

ok found '0.6685813', expected '0.6685813', error '0.0000000'

Test #4:

score: 0
Accepted
time: 15ms
memory: 3988kb

input:

1000 20
545612 774435015
828317 212155588
5294705 85926095
5648835 764528941
6159263 570820268
7177330 744079287
8446124 162286636
8735551 586528841
9263030 524140841
9505706 636254627
12111352 182639083
12750780 238494418
13149143 913232250
13382784 11485121
13699797 414697815
14263990 423817548
15...

output:

3.793210462287

result:

ok found '3.7932105', expected '3.7932105', error '0.0000000'

Test #5:

score: 0
Accepted
time: 18ms
memory: 3944kb

input:

1000 100
163505 684865289
2674260 837752883
2694530 150054425
2870791 236723512
3262597 800933455
3558503 905056977
4260872 45990808
4532415 268478572
5299228 546172100
6019224 12074540
6345109 747272172
6539452 449655551
7215852 676269961
9062989 769545718
9444242 874911191
10264016 341805234
10595...

output:

-1.860577876042

result:

ok found '-1.8605779', expected '-1.8605779', error '0.0000000'

Test #6:

score: 0
Accepted
time: 62ms
memory: 4460kb

input:

5000 10
34774 620025564
366562 278306777
446710 509672662
650220 70882120
824803 317731338
881144 257861254
1063458 61483347
1071840 639872836
1263842 30790337
1591940 346781076
1964777 814735151
2067497 63962255
2220071 379252135
2539054 428050443
2937092 423099578
3088992 959927412
3229098 9591796...

output:

134.621472807091

result:

ok found '134.6214728', expected '134.6214728', error '0.0000000'

Test #7:

score: 0
Accepted
time: 86ms
memory: 4188kb

input:

5000 20
199760 355854017
326334 308841311
562097 142603502
737215 739382649
740379 538515503
775788 515038260
817583 280515397
919169 892864353
972326 662840403
1344912 46143677
1550928 380148689
1589971 740794446
1638208 835030507
1707737 1806402
1736374 716485086
1738772 965202367
1855327 28929729...

output:

19.107398871060

result:

ok found '19.1073989', expected '19.1073989', error '0.0000000'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3872kb

input:

100 80
3642237 433728851
3835922 596838254
4822541 903206579
11786229 71614574
28051109 568783761
37988181 991770771
56927147 913182266
80808317 468372188
96532943 867642142
97069884 869788913
104938691 736691068
115294599 927608069
130086679 135340679
143622561 267761236
147838354 653078316
1483162...

output:

-45.917501529517

result:

ok found '-45.9175015', expected '-45.9175015', error '0.0000000'

Test #9:

score: 0
Accepted
time: 3ms
memory: 3876kb

input:

300 300
186421 261109479
5746147 454165382
9237830 637520496
9851923 811263876
11414218 355514230
13089969 488595547
14673543 646754325
16206307 26512314
20111827 236176303
29494991 773939650
31542488 394434870
33151870 729247973
35483496 458610267
39685298 553345644
41333867 843739706
41339284 5952...

output:

-45869.322134004819

result:

ok found '-45869.3221340', expected '-45869.3221340', error '0.0000000'

Test #10:

score: 0
Accepted
time: 10ms
memory: 3948kb

input:

1000 2
747727 310492171
1468650 713980779
3789328 757125223
5320562 240087911
5661018 585322880
5727658 166258339
9628311 1509468
9663570 644887821
9705398 201079132
11009052 79093580
11528729 273302786
14435306 891929759
16986960 794877487
17773102 990984060
19350978 246181882
19465885 427225500
23...

output:

145656.485252704180

result:

ok found '145656.4852527', expected '145656.4852501', error '0.0000000'

Test #11:

score: 0
Accepted
time: 202ms
memory: 4560kb

input:

10000 5000
11343 928311929
52379 840203434
261042 695151644
263788 172667944
364610 152184226
379806 619677738
515566 816745302
517646 466302942
540027 475750734
543982 124168292
640523 238869630
691715 468722215
705165 919447299
779673 129298873
1006841 948863833
1308410 643990798
1342527 5696458
1...

output:

-1045.873718454680

result:

ok found '-1045.8737185', expected '-1045.8737185', error '0.0000000'

Test #12:

score: 0
Accepted
time: 288ms
memory: 4496kb

input:

10000 500
83515 736933811
214681 18821934
337773 255421593
373401 682078732
542837 930642686
743115 251178260
798454 390884216
1209834 124196728
1262528 560215146
1351188 9091629
1563890 525243183
1574212 997260354
1580426 699829078
1750092 395252098
1869757 67867660
1875112 226384476
2047018 328213...

output:

-5.629902788400

result:

ok found '-5.6299028', expected '-5.6299028', error '0.0000000'

Test #13:

score: 0
Accepted
time: 305ms
memory: 4492kb

input:

10000 300
1639 469147828
114667 8224138
144408 364515807
212973 961202084
398743 285809740
496841 927819708
534650 867558923
686967 588702382
696690 666164443
726922 781870146
872473 615520296
898161 178383389
985406 97264277
996652 703675454
1254375 530922354
1573412 745036174
1637763 177874295
167...

output:

-1.304150527632

result:

ok found '-1.3041505', expected '-1.3041505', error '0.0000000'

Test #14:

score: 0
Accepted
time: 298ms
memory: 4488kb

input:

10000 200
24361 355989436
67308 334706995
197996 808393732
208836 116843625
567811 484127866
694262 618656785
788342 790194385
849652 136657098
1029137 924171800
1203341 168259404
1211974 844956962
1214043 637541127
1420445 759167413
1655236 915436195
1657793 262449701
1691654 725474596
1767520 8976...

output:

-0.114468865279

result:

ok found '-0.1144689', expected '-0.1144689', error '0.0000000'

Test #15:

score: 0
Accepted
time: 282ms
memory: 4540kb

input:

10000 100
448934 906394555
475014 997626342
590053 178642728
875628 903888948
1212211 346009502
1241514 309493863
1340826 712829848
1680222 758240743
1794126 477146449
1817597 186052442
1981543 779426336
2021852 433135353
2185476 494699476
2298672 422164227
2516850 625380828
2646484 337316798
267075...

output:

1.035376804971

result:

ok found '1.0353768', expected '1.0353768', error '0.0000000'

Test #16:

score: 0
Accepted
time: 231ms
memory: 4600kb

input:

10000 50
40110 141597180
41162 930485122
87106 57859547
129179 279497823
217282 102811622
246011 688060074
527945 830469708
674775 425660310
781249 284422288
845105 393707471
1003702 918990189
1121790 534007402
1337016 917493002
1440969 636045451
1729947 231052670
1779758 199172396
1990895 270436931...

output:

5.115538367405

result:

ok found '5.1155384', expected '5.1155384', error '0.0000000'

Test #17:

score: 0
Accepted
time: 171ms
memory: 4500kb

input:

10000 20
192005 992303174
386824 5538930
652843 617355627
665819 922060802
675553 291515142
791249 384248576
854934 231142457
926022 596717008
932239 945932944
969019 474307451
1374561 126586755
1567083 106513004
1629151 116861834
1670295 988693473
1775518 799130552
1792436 888344340
1820264 3853242...

output:

41.567725410073

result:

ok found '41.5677254', expected '41.5677254', error '0.0000000'

Test #18:

score: 0
Accepted
time: 127ms
memory: 4404kb

input:

10000 10
266996 609205171
273102 735589575
277177 347655580
387543 606270266
469806 638663697
782692 72510150
796356 424656429
870781 260446185
926881 906882617
1343887 6609329
1382474 430796513
1550455 62337302
1552339 109538657
1629503 994097318
1808731 767302009
1877069 710955532
2206272 16406618...

output:

299.452481593818

result:

ok found '299.4524816', expected '299.4524816', error '0.0000000'

Test #19:

score: 0
Accepted
time: 113ms
memory: 4408kb

input:

10000 8
88029 227530654
223658 46422449
264166 625625697
310448 286795635
454903 177457515
464676 839404426
687127 463087924
691931 190423638
704573 856226776
765895 482811447
768088 644745751
835500 427038249
919699 469313878
1032714 947023480
1152691 976821799
1197844 123594183
1286309 353740491
1...

output:

628.852979485080

result:

ok found '628.8529795', expected '628.8529795', error '0.0000000'

Test #20:

score: 0
Accepted
time: 91ms
memory: 4476kb

input:

10000 5
62217 249235177
306503 34074294
477055 572914538
702905 839767773
704209 612222410
816080 392889606
861062 830566450
972418 999799224
1062852 573719854
1105278 478171882
1109703 803913526
1131824 820380955
1232243 740998431
1346238 6361814
1557725 497005895
1644920 318176224
1675339 14779790...

output:

3264.755751370949

result:

ok found '3264.7557514', expected '3264.7557514', error '0.0000000'

Test #21:

score: 0
Accepted
time: 123ms
memory: 4696kb

input:

10000 2
81106 607376188
121099 653129920
571348 183766890
852412 97772619
885397 341954595
972399 314971005
1253363 493012266
1295891 104142101
1298100 659809152
1322651 842128537
1432357 889452372
1451236 918756370
1486954 86311912
1536631 770732857
1592430 17189991
1616977 439129337
1724413 646888...

output:

12931122.782887795940

result:

ok found '12931122.7828878', expected '12931122.7792642', error '0.0000000'

Test #22:

score: -100
Time Limit Exceeded

input:

100000 50000
15057 358350989
39346 497842396
51813 37907067
52457 435919654
53100 875724585
58397 718257424
59957 37620444
67204 427984803
74005 329917739
74035 317952573
75181 793673458
79739 677360131
90807 331908646
102249 97003766
103081 951437983
105105 433577588
105745 722249067
111137 8229696...

output:


result: