QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#443862#8648. Towerarbuzick#25 114ms12692kbC++202.9kb2024-06-15 16:42:122024-06-15 16:42:14

Judging History

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

  • [2024-06-15 16:42:14]
  • 评测
  • 测评结果:25
  • 用时:114ms
  • 内存:12692kb
  • [2024-06-15 16:42:12]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

constexpr long long inf = (long long)1e18 + 7;

constexpr int maxval = 1e6 + 5;

long long dp[maxval];

void solve() {
    int n, q;
    cin >> n >> q;
    long long d;
    int a, b;
    cin >> d >> a >> b;
    vector<pair<long long, long long>> lr(n);
    for (int i = 0; i < n; ++i) {
        cin >> lr[i].first >> lr[i].second;
        lr[i].second++;
    }
    if (b >= d * a) {
        vector<pair<pair<long long, long long>, long long>> ans;
        ans.emplace_back(make_pair(0, lr[0].first), 0);
        for (int i = 0; i < n; ++i) {
            long long nxt = inf;
            if (i + 1 < n) {
                nxt = lr[i + 1].first;
            }
            long long mn = lr[i].second - d;
            int pos = lower_bound(ans.begin(), ans.end(), make_pair(make_pair(mn, 0LL), 0LL)) - ans.begin();
            long long start = inf;
            long long cost = inf;
            if (pos < (int)ans.size()) {
                start = ans[pos].first.first;
                cost = ans[pos].second;
            }
            if (pos > 0) {
                pos--;
                if (ans[pos].first.second > mn) {
                    start = mn;
                    cost = min(cost, ans[pos].second);
                }
            };
            if (start + d < nxt) {
                ans.emplace_back(make_pair(start + d, nxt), cost + 1);
            }
        }
        while (q--) {
            long long x;
            cin >> x;
            int pos = lower_bound(ans.begin(), ans.end(), make_pair(make_pair(x + 1, 0LL), 0LL)) - ans.begin() - 1;
            if (x < ans[pos].first.second) {
                cout << x * a + (b - d) * ans[pos].second << '\n';
            } else {
                cout << -1 << '\n';
            }
        }
    } else {
        for (int i = 0; i < maxval; ++i) {
            dp[i] = inf;
        }
        for (int i = 0; i < n; ++i) {
            for (int j = lr[i].first; j < lr[i].second; ++j) {
                dp[j] = inf * 2;
            }
        }
        dp[0] = 0;
        for (int i = 0; i < maxval; ++i) {
            if (dp[i] != -1) {
                if (i + 1 < maxval && dp[i + 1] != inf * 2) {
                    dp[i + 1] = min(dp[i + 1], dp[i] + a);
                }
                if (i + d < maxval && dp[i + d] != inf * 2) {
                    dp[i + d] = min(dp[i + d], dp[i] + b);
                }
            }
        }
        while (q--) {
            long long x;
            cin >> x;
            if (dp[x] >= inf) {
                cout << -1 << '\n';
            } else {
                cout << dp[x] << '\n';
            }
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 5
Accepted
time: 34ms
memory: 11452kb

input:

2000 200000
500 66309 387245
91 122
793 1029
1127 1131
1304 1611
2007 2039
2601 2701
2906 3052
3253 3263
3495 3609
4157 4225
4283 4283
4757 4766
4786 4847
4885 5086
5326 5342
5607 5750
5847 5877
6093 6230
6548 6793
7206 7308
7413 7419
7752 7780
8244 8410
8501 8515
9335 9447
9512 9514
9602 9906
10076...

output:

-1
-1
1545376776
-1
1355518146
-1
-1
1538578776
1124179254
736677313
275840218
-1
314646902
120181124
592802647
1470145222
1194355416
630012616
541479470
1380556431
748297307
1579324340
83071935
-1
547672724
766967273
940718126
967114418
448357717
-1
208077708
264694996
68332763
-1
699361243
1542138...

result:

ok 200000 lines

Test #2:

score: 5
Accepted
time: 31ms
memory: 11460kb

input:

2000 200000
500 45649 229891
123 232
663 994
1023 1041
1065 1065
1523 1542
1962 1983
2044 2066
2449 2453
2589 2591
2788 2810
3207 3418
3666 3685
3944 3945
4256 4320
4699 4706
4915 4950
5196 5207
5271 5545
5705 5707
5867 6034
6273 6328
6364 6380
6764 6787
6974 7007
7363 7365
7632 7648
7754 7924
7954 ...

output:

-1
-1
1044862158
349767467
-1
-1
-1
-1
534260754
853076992
514160380
514034955
-1
-1
680989150
557376047
-1
410302211
-1
-1
14156128
-1
-1
656642980
-1
335413929
465525211
1047741337
1007928386
-1
183280077
-1
842399625
553981561
-1
-1
486838795
823208939
597570650
68518820
-1
-1
36379839
-1
4959492...

result:

ok 200000 lines

Test #3:

score: 0
Wrong Answer
time: 28ms
memory: 3652kb

input:

2000 200000
500 11 228852
288 470
648 922
1193 1288
1509 1516
1792 1915
2023 2061
2443 2477
2512 2693
2735 2860
3176 3196
3260 3363
3622 3658
3939 3988
4177 4223
4470 4541
4640 4789
4812 4850
5167 5246
5443 5594
5692 5804
5875 5982
6265 6286
6416 6609
6816 6833
6928 7130
7298 7305
7401 7403
7778 781...

output:

63099766
1883455
197465572
97566804
82088946
192546144
129229653
-1
121727183
162519071
109762913
162051895
108118337
-1
169783718
-1
168609783
-1
3053793
150089891
-1
77398618
-1
-1
-1
111868978
-1
114919548
166973919
68728527
174708140
131807679
171660122
-1
190440233
155007042
42940050
-1
1589977...

result:

wrong answer 1st lines differ - expected: '61754766', found: '63099766'

Subtask #2:

score: 0
Runtime Error

Test #29:

score: 0
Runtime Error

input:

1938 1960
999999 47694 9291
2883622 3085639
3674880 3745876
9982198101 9982517489
19960889157 19960925795
19962228551 19962276101
19964301694 19964730442
19964826417 19965369252
19965984922 19966442459
19968019821 19968213820
19968334967 19968392242
19968426638 19968840337
19969017519 19969109591
19...

output:


result:


Subtask #3:

score: 25
Accepted

Test #44:

score: 25
Accepted
time: 77ms
memory: 12692kb

input:

198085 196577
999999 1 999999
562622 895604
1799586 1975565
2518299 2941986
4934097 5403130
5755102 5996130
6036200 6112534
6391882 6431514
6451793 6555786
6613625 6621089
7130933 7204522
7335426 7522555
7748545 7784568
8184979 8494887
9066856 9178094
9303615 9384897
9716200 9719420
11693951 1183563...

output:

27793636591
139076373265
-1
-1
164554928593
340203577240
767735640886
-1
808488370439
777661458222
428941062963
-1
756913262477
860152123456
-1
734774231229
724225013316
184932545705
418133621292
-1
890908770677
450977017227
806542610691
-1
898938307262
536837237896
805921470285
-1
588880769556
-1
4...

result:

ok 196577 lines

Test #45:

score: 25
Accepted
time: 91ms
memory: 12532kb

input:

199371 195400
999999 1 999999
4612523 4947496
5154685 5535111
6001135 6243639
7356800 7512564
7752763 7797747
8964902 8981715
9750529 9966044
9975655 10525517
16728399 17323380
17812655 17876446
17926768 18006465
18054955 18353713
18566302 18650151
19483683 19787610
20585307 20768207
22240113 222443...

output:

-1
621180105200
-1
-1
461780052274
772236852813
710455468422
730649315181
758552247311
190536170737
472110590707
660933061395
107617202142
917915550413
-1
252526045269
-1
730423595734
-1
-1
-1
-1
-1
-1
-1
276664132078
392648881685
207163529590
748682653117
622053824210
485855702116
-1
661004479399
-...

result:

ok 195400 lines

Test #46:

score: 25
Accepted
time: 92ms
memory: 12420kb

input:

198278 196370
999999 1 999999
161975 250088
790789 822594
1044921 1160804
1182774 1186404
1212165 1493435
1928841 1935221
2686095 2994407
3085371 3137281
4151843 4199695
4797370 4807889
7089261 7293018
7469787 8294563
8639586 9028758
9535294 9647237
10261792 10434860
14068523 14148691
14245117 14573...

output:

107006124752
127121450263
719480563528
-1
97915594959
-1
272093640421
-1
-1
779112437224
-1
278064103799
-1
-1
94629533880
-1
518947410699
295938119924
-1
286734572810
-1
462315178138
-1
656398601363
-1
515972463880
-1
-1
463731627587
29815838997
503713954019
894142823925
386885082072
675276164984
4...

result:

ok 196370 lines

Test #47:

score: 25
Accepted
time: 86ms
memory: 12348kb

input:

190308 196088
999999 1 999999
1589316 1719530
2162548 2518931
2629052 2984381
3086913 3353461
3455225 3455282
5432539 5481306
5850838 6295339
6986760 7082054
7925601 7941270
8188318 8209952
8326216 8494288
8898926 9225853
9795199 10273087
10964225 10973927
11365962 11546260
11612346 11669740
1177897...

output:

335994513998
-1
756345517990
63844676033
816674895005
95793949773
448915126326
961367036898
926970280278
315502814398
608736217929
-1
-1
890007920329
940210562473
619071423487
926609908048
149362280657
571340649004
777210538008
256673125898
-1
349176941798
648540718499
938038904114
-1
459037706019
4...

result:

ok 196088 lines

Test #48:

score: 25
Accepted
time: 93ms
memory: 12488kb

input:

197660 195976
999999 1 999999
13343 692586
752194 983954
2435751 2945408
5413895 5421536
5520870 5720635
6959165 7086977
8622293 8847227
9660334 9823364
9835842 10252958
10929283 11277121
13750555 13810298
16634199 16637075
16870329 16970353
17336772 17653119
17725964 17833010
17958933 18336713
1890...

output:

521609825924
-1
932434325540
43425485771
757783622284
-1
601903818129
254437477178
819025671166
-1
236626854386
-1
257471432852
235245317149
117469362126
373027753560
-1
385486221028
-1
945304016581
-1
-1
375101203285
153888061031
-1
520898561028
189327508417
-1
587569604527
108513358547
-1
11696540...

result:

ok 195976 lines

Test #49:

score: 25
Accepted
time: 114ms
memory: 12544kb

input:

200000 200000
2000 1 2000
630 1632
1876 2158
2711 3735
4234 4856
5509 5902
13850 14242
15159 15716
17404 18103
19901 20024
20304 21089
21221 21344
22180 22985
23130 23236
30082 30591
30689 31072
33612 33935
40527 42290
45383 46190
46716 46800
47173 47263
47557 48161
57768 59567
59738 59853
60060 605...

output:

79991745323
789936142800
949975423013
729941161919
-1
-1
-1
519967821113
429970845198
639947050982
909952551269
399975684295
919965655725
909951170493
-1
589951000213
269982121508
389969423060
59994813183
379961893157
659944665315
-1
249979594110
499967867639
209979928363
519968145089
199982438348
8...

result:

ok 200000 lines

Test #50:

score: 25
Accepted
time: 85ms
memory: 12572kb

input:

200000 200000
2000 1 2000
260 867
876 1570
2586 2588
2630 2673
5473 6136
6816 7919
8895 9594
10867 11177
11588 11926
11969 12540
14072 14360
17570 18053
18756 19104
20252 20268
20514 20850
20971 21741
23959 24092
24462 24567
25212 25711
28968 29583
30188 30283
30780 31258
34284 34620
35552 35705
380...

output:

-1
9997494709
239984588464
10002561642
-1
310031121401
820005048898
-1
239980275729
470006769653
740015016291
240003164340
239998669154
239988346465
29996548578
-1
-1
90006192595
239988759589
-1
90005179717
690002714628
80001200307
790011724101
240001187799
690005227176
639999528978
-1
-1
4300175646...

result:

ok 200000 lines

Test #51:

score: 25
Accepted
time: 105ms
memory: 12500kb

input:

200000 200000
2000 1 2000
4457 4812
5482 5543
6836 7518
7558 7879
16521 16744
17677 17817
17916 17952
18233 18735
22630 22876
22954 23607
31841 33245
33432 33510
34384 34614
44971 45885
51032 51076
53548 53978
53980 54480
54995 55041
56164 57051
58728 59306
60549 60759
62649 62801
63829 64019
68138 ...

output:

-1
-1
490005213735
389983980028
-1
479993577366
269964928122
30006145533
589998466131
209977981338
709974711240
589993534516
-1
909979446385
530007635029
-1
909972674899
-1
849970905468
520005647906
-1
279969864933
299980247051
-1
279977883884
-1
510008135845
89998515208
-1
-1
-1
510006963301
369988...

result:

ok 200000 lines

Test #52:

score: 25
Accepted
time: 94ms
memory: 12688kb

input:

200000 200000
1000000 1 1000000
1201721 1894242
3016023 3044124
3467614 3538694
3868596 3901358
5781073 5925868
6188800 6413742
6683123 6948980
9324814 9508614
9797754 9926873
11701859 11712194
12520205 12627404
12987536 13383402
14184412 14404606
15290399 15593444
16186265 16463964
17416648 1774610...

output:

154980181226
3053320078
-1
116668888082
52271638839
-1
194799064164
-1
135756169612
35949188430
-1
101574878576
177681636714
-1
23671095214
172261625503
67298510105
-1
175627528003
28969352849
196466288166
192245483818
100571063417
-1
12133638153
65877759591
-1
-1
118589141668
215552746469
-1
-1
143...

result:

ok 200000 lines

Test #53:

score: 25
Accepted
time: 98ms
memory: 12492kb

input:

200000 200000
1000000 1 1000000
170004 855149
2051762 2466419
3042850 3311890
4045589 4929749
5434536 5840730
6619205 6629299
6732346 7131471
8450452 8495454
8766287 8983021
9117442 9301222
9425194 9857355
14712346 15056382
15443258 15607917
16976863 17104932
18404155 19086936
19517213 19643464
2176...

output:

13535930147
22930364103
-1
-1
200106537302
194624823376
-1
208412563639
-1
38366854635
54568152392
145580423084
89318146708
158033508663
-1
-1
62672221678
115668089771
-1
42043383736
67774069552
55883146103
-1
185303429007
63170324973
106302694809
16821998417
217192371056
154398812901
170874356974
3...

result:

ok 200000 lines

Test #54:

score: 25
Accepted
time: 61ms
memory: 7300kb

input:

200000 200000
50 1 50
28 31
35 38
135 160
275 283
304 323
404 407
429 434
507 520
530 549
577 578
588 602
611 614
628 631
720 727
730 736
746 754
767 767
784 797
881 900
988 1009
1117 1133
1175 1192
1209 1218
1232 1232
1249 1250
1338 1349
1476 1486
1500 1515
1522 1547
1589 1616
1640 1644
1677 1683
1...

output:

-1
-1
-1
-1
-1
-1
-1
96813
-1
-1
-1
-1
99999906396
79999852694
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
79999765785
-1
-1
-1
-1
-1
-1
20000052620
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
79999887656
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
79999727135
25633
120000236130...

result:

ok 200000 lines

Test #55:

score: 25
Accepted
time: 59ms
memory: 6644kb

input:

200000 200000
50 1 50
19 20
38 43
59 93
107 137
343 347
361 363
616 626
683 686
692 707
709 716
750 783
807 807
947 950
966 968
980 997
1021 1032
1064 1079
1111 1148
1174 1189
1198 1204
1265 1280
1288 1309
1320 1342
1484 1491
1518 1526
1539 1563
1567 1571
1606 1608
1642 1642
1644 1644
1655 1658
1831...

output:

-1
40000020068
-1
-1
-1
-1
-1
-1
-1
-1
39999950681
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 200000 lines

Test #56:

score: 25
Accepted
time: 63ms
memory: 6608kb

input:

200000 200000
50 1 50
4 5
7 14
23 23
25 28
38 46
80 111
270 271
303 321
354 362
374 390
396 399
431 431
444 452
454 454
456 468
497 505
567 579
585 586
718 721
784 796
898 917
933 933
944 949
1001 1032
1059 1068
1074 1078
1166 1169
1171 1188
1203 1206
1242 1254
1398 1415
1420 1437
1465 1469
1582 160...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
39999747777
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
49999721223
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
49999702499
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

ok 200000 lines

Subtask #4:

score: 0
Skipped

Dependency #1:

0%