QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#719782#8648. Towerhhoppitree0 732ms42808kbC++174.2kb2024-11-07 08:52:002024-11-07 08:52:00

Judging History

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

  • [2024-11-07 08:52:00]
  • 评测
  • 测评结果:0
  • 用时:732ms
  • 内存:42808kb
  • [2024-11-07 08:52:00]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

long long res[N], id[N], mn[1 << 21], lz[1 << 21];

void build(int k, int l, int r) {
    mn[k] = (l == 1 ? 0 : 3e18);
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(k << 1, l, mid);
    build(k << 1 | 1, mid + 1, r);
}

void pushdown(int k) {
    if (!lz[k]) return;
    mn[k << 1] = 3e18, lz[k << 1] = 1;
    mn[k << 1 | 1] = 3e18, lz[k << 1 | 1] = 1;
    lz[k] = 0;
}

void modify(int k, int l, int r, int x, int y) {
    if (l > y || r < x) return;
    if (l >= x && r <= y) {
        mn[k] = 3e18, lz[k] = 1;
        return;
    }
    pushdown(k);
    int mid = (l + r) >> 1;
    modify(k << 1, l, mid, x, y);
    modify(k << 1 | 1, mid + 1, r, x, y);
    mn[k] = min(mn[k << 1], mn[k << 1 | 1]);
}

void update(int k, int l, int r, int x, long long y) {
    mn[k] = min(mn[k], y);
    if (l == r) return;
    pushdown(k);
    int mid = (l + r) >> 1;
    if (x <= mid) update(k << 1, l, mid, x, y);
    else update(k << 1 | 1, mid + 1, r, x, y);
}

long long query(int k, int l, int r, int x, int y) {
    if (l > y || r < x) return 3e18;
    if (l >= x && r <= y) return mn[k];
    pushdown(k);
    int mid = (l + r) >> 1;
    return min(query(k << 1, l, mid, x, y), query(k << 1 | 1, mid + 1, r, x, y));
}

signed main() {
    int n, q;
    long long D, A, B;
    scanf("%d%d%lld%lld%lld", &n, &q, &D, &A, &B);
    vector< pair<long long, int> > p;
    vector<long long> lsh;
    for (int i = 1; i <= n; ++i) {
        long long l, r; scanf("%lld%lld", &l, &r);
        p.push_back({l, 0}), p.push_back({r + 1, 0});
        lsh.push_back(l % D), lsh.push_back((r + 1) % D);
    }
    lsh.push_back(0), lsh.push_back(D - 1);
    p.push_back({0, q + 1});
    for (int i = 1; i <= q; ++i) {
        long long x; scanf("%lld", &x);
        id[i] = x;
        p.push_back({x, i});
        lsh.push_back(x % D);
        res[i] = 3e18;
    }
    sort(lsh.begin(), lsh.end());
    lsh.erase(unique(lsh.begin(), lsh.end()), lsh.end());
    sort(p.begin(), p.end());
    auto getId = [&](long long x) {
        return lower_bound(lsh.begin(), lsh.end(), x) - lsh.begin() + 1;
    };
    build(1, 1, lsh.size());
    set< pair<int, int> > S = {{1, lsh.size()}};
    long long tag = 0;
    for (int m = p.size(), i = 0, j, nw = 0; i < m; ) {
        j = i;
        auto preMax = [&](int x) {
            int val = 1;
            if (!S.empty() && (S.begin() -> first) <= x) {
                auto it = --S.lower_bound({x + 1, 0});
                val = (it -> second) + 1;
            }
            update(1, 1, lsh.size(), x, query(1, 1, lsh.size(), val, x));
        };
        while (j < m && p[j].first / D == p[i].first / D) {
            preMax(getId(p[j++].first % D));
        }
        preMax(lsh.size());
        if (i) update(1, 1, lsh.size(), 1, query(1, 1, lsh.size(), lsh.size(), lsh.size()) + A * D - B);
        S.clear();
        int lst = 1;
        vector< pair<long long, int> > qr;
        while (i < j) {
            int tid = getId(p[i].first % D);
            if (nw) {
                modify(1, 1, lsh.size(), lst, tid - 1);
                if (lst <= tid - 1) S.insert({lst, tid - 1});
            }
            nw ^= !p[i].second;
            lst = tid;
            if (p[i].second) qr.push_back({p[i].first, p[i].second});
            ++i;
        }
        if (nw) {
            modify(1, 1, lsh.size(), lst, lsh.size());
            S.insert({lst, lsh.size()});
        }
        for (auto [x, y] : qr) {
            int tid = getId(x % D);
            preMax(tid), res[y] = tag + query(1, 1, lsh.size(), tid, tid);
        }
        if (i != m && p[i].first / D != p[i - 1].first / D + 1) {
            if (nw) break;
            S.clear(), preMax(lsh.size()), update(1, 1, lsh.size(), 1, query(1, 1, lsh.size(), lsh.size(), lsh.size()) + A * D - B);
            tag += (p[i].first / D - p[i - 1].first / D - 1) * min(A * D - B, 0ll);
        }
    }
    for (int i = 1; i <= q; ++i) {
        if (res[i] > 2e18) puts("-1");
        else printf("%lld\n", res[i] + id[i] % D * A + id[i] / D * B);
    }
    return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 5
Accepted
time: 149ms
memory: 15108kb

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: 146ms
memory: 14876kb

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: 5
Accepted
time: 149ms
memory: 13688kb

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:

61754766
1843455
193255572
95486804
80338946
188441144
126474653
-1
119132183
159054071
107422913
158596895
105813337
-1
166163718
-1
165014783
-1
2988793
146889891
-1
75748618
-1
-1
-1
109483978
-1
112469548
163413919
67263527
170983140
128997679
168000122
-1
186380233
151702042
42025050
-1
1556077...

result:

ok 200000 lines

Test #4:

score: 5
Accepted
time: 134ms
memory: 15500kb

input:

2000 200000
500 123 507044
13 349
778 805
1289 1419
2069 2074
2126 2129
2299 2392
2629 2629
3035 3054
3171 3184
3225 3381
3967 4100
4222 4225
4432 4603
4741 4745
4972 5123
5239 5245
5412 5530
5737 5757
5859 6162
6286 6289
6452 6542
6820 6825
6940 6974
7327 7328
7686 7781
8122 8169
8499 8909
8957 896...

output:

23238378
-1
320316781
492915201
-1
118374346
-1
118865646
-1
27397189
413766267
33059543
89523552
84434908
75590808
178982529
452655813
119364449
76127495
-1
-1
296028030
320308540
475355659
-1
210903877
288320772
388500820
-1
149739573
428228318
-1
-1
-1
-1
478454749
-1
-1
-1
-1
268399317
-1
310981...

result:

ok 200000 lines

Test #5:

score: 5
Accepted
time: 143ms
memory: 15108kb

input:

2000 200000
500 367 183500
395 476
616 705
1068 1085
1392 1462
1898 2004
2105 2124
2266 2553
2678 2684
2845 2855
3145 3188
3497 3630
3705 3708
3857 3995
4221 4223
4405 4642
4724 4730
4993 5199
5224 5225
5325 5637
5722 5735
6111 6152
6322 6341
6464 6694
6764 6838
7013 7174
7249 7261
7423 7713
7803 78...

output:

-1
81789987
195275562
134586974
172718274
-1
77090919
-1
169680615
26763842
81273618
74582841
-1
-1
164912918
-1
45100263
25295842
5720062
138829861
-1
23310005
142354162
158449681
-1
43546018
5823556
-1
-1
-1
-1
125462620
-1
25779548
121436630
4706408
-1
-1
-1
87290583
-1
47107386
94590213
17249256...

result:

ok 200000 lines

Test #6:

score: 5
Accepted
time: 172ms
memory: 29868kb

input:

195716 197150
20 41515 610194
34 34
36 36
38 38
40 40
42 42
44 44
46 46
83 83
85 85
87 87
89 89
91 91
93 93
95 95
97 97
99 99
104 104
106 106
108 108
110 110
112 112
114 115
118 118
120 120
132 132
134 134
136 136
138 138
140 140
142 142
144 144
146 146
148 148
150 150
175 175
177 177
179 179
181 18...

output:

27145048833
-1
20311977145
5823894704
12611222982
10375331362
-1
4666825214
8294213599
7946746140
15043381651
12084461892
2564209663
-1
2889605968
30371230407
13809822492
10059353510
20452787039
-1
186985672
-1
-1
-1
14667164575
21798169916
2551478619
-1
2357959404
24230797781
5359696913
11480637002...

result:

ok 197150 lines

Test #7:

score: 5
Accepted
time: 186ms
memory: 29704kb

input:

194401 196154
20 81884 184176
27 27
29 29
31 31
33 33
35 35
37 37
39 39
41 41
43 43
45 45
103 106
110 110
114 115
119 119
121 121
123 123
125 126
128 128
130 130
132 132
135 135
137 137
170 171
173 173
175 175
179 179
181 181
183 184
186 186
203 203
205 205
207 207
210 210
212 212
214 214
216 216
22...

output:

-1
7397081928
2079536780
1740817712
7985105512
8791917840
-1
2108310564
3818312684
3403790452
-1
-1
7282843676
8094061364
8075949632
-1
4202973208
-1
5158569260
5191129360
-1
5769244224
-1
5536679820
7825620684
4417835300
10616377912
-1
7443886064
5554791552
7631714344
4169124128
10019841164
8876887...

result:

ok 196154 lines

Test #8:

score: 0
Wrong Answer
time: 181ms
memory: 29180kb

input:

197806 197356
20 29644 637771
3 3
5 5
7 7
9 9
11 11
13 13
15 15
17 17
19 19
21 21
71 71
73 73
75 75
77 77
79 79
81 81
83 83
85 85
87 87
89 89
94 94
96 96
98 98
100 100
102 102
104 104
106 107
122 122
124 124
126 126
128 128
131 131
133 133
135 135
156 156
158 158
160 160
163 163
165 165
216 216
218 ...

output:

-1
16953378629
16957382269
-1
-1
30899334898
986697668
7738690329
14738925617
1812218996
-1
7367095512
26984533449
2970332934
-1
-1
-1
-1
26579462056
16920283175
2133941555
17190470809
-1
26650871158
29684195148
812559250
25298649743
27419867222
29698326889
13375696131
1926381599
9818162150
-1
86856...

result:

wrong answer 2nd lines differ - expected: '16958900222', found: '16953378629'

Subtask #2:

score: 0
Wrong Answer

Test #29:

score: 38
Accepted
time: 3ms
memory: 10212kb

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:

2629532778036
1625568767553
-1
-1
-1
931487890158
217249154424
-1
3376854733974
453288498306
1144114552242
194772660096
116508067359
1965611506731
2806098123096
3404924462019
1737385084617
1649786307423
-1
3043407203193
2248403158668
-1
-1
538903132932
2740777563264
-1
3173320399527
-1
-1
2616652920...

result:

ok 1960 lines

Test #30:

score: 38
Accepted
time: 0ms
memory: 8144kb

input:

1837 1989
999999 41963 54422
9980315942 9981214568
9981614247 9981843710
9982430252 9982433585
9983182843 9983561789
9984404759 9984499318
9984655332 9984859904
9985420428 9985717345
9985762820 9985867258
9986396224 9986498679
9986533284 9986947589
9987502488 9988096750
9989096806 9989207060
9989676...

output:

-1
2554711024271
-1
977926019067
3238028322568
201257084557
-1
3205448836431
387280383252
-1
-1
-1
1216454626736
823964810173
117884656882
2669122054316
734561443433
1448900485845
3203724783289
796733108264
883217412007
-1
-1
147443422287
2027763666999
2378863303928
-1
-1
3091310739595
2261110540233...

result:

ok 1989 lines

Test #31:

score: 0
Wrong Answer
time: 6ms
memory: 8460kb

input:

1985 1968
999999 1 1000000
9978505229 9979247763
9979301501 9979397117
9981449577 9981533536
9981765886 9982271507
9983158890 9983349521
9983843213 9984416208
9985032631 9985197994
9987158017 9987185683
9987259105 9988030168
9988487256 9988529335
9988581372 9988946469
9989439295 9989530721
998958116...

output:

-1
-1
700140493110
-1
489978355295
300086770519
-1
559982430027
130003223090
640114157938
450000487707
740106556827
29952519870
-1
240105075076
350026198680
170023233339
-1
700129344014
559996047499
29958778066
-1
519963146742
489976670655
610079022286
80061443942
479963278386
39959493311
1399929819...

result:

wrong answer 3rd lines differ - expected: '700140493470', found: '700140493110'

Subtask #3:

score: 0
Wrong Answer

Test #44:

score: 0
Wrong Answer
time: 732ms
memory: 42808kb

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:

wrong answer 1506th lines differ - expected: '-1', found: '341000800192'

Subtask #4:

score: 0
Skipped

Dependency #1:

0%