UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#173082#3151. Convex Hullli02011009721ms32456kbC++113.2kb2023-07-11 11:51:022023-07-11 13:06:52

answer

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define ROF(i, a, b) for (int i = a; i >= b; --i)

inline int read() {
    int f = 1, x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

using namespace std;

const int N = 2e6 + 7, mod = 1e9 + 7;
ll ksm(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
int n, d[N], dd[N];
ll L, x[N];
ll pw[N], res;
ll qsum(int l, int r) {
    if (l <= r) return pw[r - l];
    return pw[r + n - l];
}
int buc[20], cm, z[20];
ll qs(vector<pair<int, int>> &hv, int a, int b) {
    int sum = 0;
    cm = 0;
    buc[++cm] = 0, buc[++cm] = n;
    for (auto &t : hv) {
        buc[++cm] = t.first - 1, buc[++cm] = t.second;
    }
    sort(buc + 1, buc + cm + 1);
    cm = unique(buc + 1, buc + cm + 1) - buc - 1;
    FOR(i, 1, cm) z[i] = 0;
    for (auto &t : hv) {
        int l = t.first, r = t.second;
        FOR(i, 1, cm) {
            if (l <= buc[i] && buc[i] <= r) {
                ++z[i];
            }
        }
    }
    FOR(i, 2, cm) {
        if (z[i] == 0) return 0;
        if (z[i] == 2) sum += buc[i] - buc[i - 1] - (buc[i - 1] < a && a <= buc[i]) - (buc[i - 1] < b && b <= buc[i]);
    }
    return pw[sum];
}
ll qsum(int l, int r, int L, int R, int a, int b) {  // l < L
    vector<pair<int, int>> hv;
    if (l <= r) {
        hv.push_back({l, r});
    } else {
        hv.push_back({l, n}), hv.push_back({1, r});
    }
    if (L <= R) {
        hv.push_back({L, R});
    } else {
        hv.push_back({L, n}), hv.push_back({1, R});
    }
    return qs(hv, a, b);
}
ll solve1() {
    ll res = 1;
    FOR(i, 1, n) { res = (res + qsum(i, d[i])) % mod; }
    return res * 2 % mod;
}
ll solve2() {
    ll res = 0;
    FOR(i, 1, n) {
        int p = (i - 1 < 1 ? n : i - 1), q = (d[i] + 1 > n ? 1 : d[i] + 1);
        res = (res + qsum(i, d[i], dd[p], p, i, p) + qsum(i, d[i], q, d[q], i, q) - 1 + mod) % mod;
    }
    return res;
}
void check() {
    FOR(i, 1, n - 1) {
        if ((x[i + 1] - x[i]) * 2 >= L) {
            puts("0");
            exit(0);
        }
    }
    if ((x[1] + L - x[n]) * 2 >= L) {
        puts("0");
        exit(0);
    }
}
int main() {
    // freopen("c.in", "r", stdin);
    // freopen("c.out", "w", stdout);
    n = read(), L = read();
    FOR(i, 1, n) x[i] = read();
    check();
    FOR(i, 1, n) x[n + i] = x[i] + L;
    pw[0] = 1;
    FOR(i, 1, n) pw[i] = pw[i - 1] * 2 % mod;
    for (int i = 1, j = 1; i <= n; ++i) {
        while (j < n * 2 && (x[j + 1] - x[i]) * 2 < L) ++j;
        d[i] = j > n ? j - n : j;
        dd[i] = j + 1;
        if ((x[j + 1] - x[i]) * 2 == L) ++dd[i];
        if (dd[i] > n) dd[i] -= n;
    }
    res = (pw[n] - solve1() + solve2() + mod) % mod;
    // printf("%lld\n", res);
    printf("%lld\n", res * ksm(pw[n], mod - 2) % mod);
    return 0;
}

详细

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 0ms
memory: 1144kb

input:

1 338327625
233370802

output:

0

result:

ok 1 number(s): "0"

Test #2:

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

input:

2 354032343
25445033 95400877

output:

0

result:

ok 1 number(s): "0"

Test #3:

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

input:

3 494259722
45895191 52756441 111187988

output:

0

result:

ok 1 number(s): "0"

Test #4:

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

input:

4 885497817
91430998 103481542 307555388 604271006

output:

0

result:

ok 1 number(s): "0"

Test #5:

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

input:

19 498535581
11446236 61220874 70088068 110079153 120427018 169152782 218770800 256038787 264278513 ...

output:

693847662

result:

ok 1 number(s): "693847662"

Test #6:

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

input:

20 857047361
2882336 109619560 130672680 249207458 290165432 302306743 396543010 500846269 589542410...

output:

30860902

result:

ok 1 number(s): "30860902"

Test #7:

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

input:

16 896598032
385527 23638360 211509055 246262569 383282908 399979537 412721715 429936164 436559708 4...

output:

146911623

result:

ok 1 number(s): "146911623"

Test #8:

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

input:

20 809012240
5201278 17008104 99890217 111288174 146758265 261393101 301223338 338799166 356944721 4...

output:

618438726

result:

ok 1 number(s): "618438726"

Test #9:

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

input:

19 898545014
18307524 46891945 121230342 237127635 240311752 326861518 410094554 462981654 509795635...

output:

586189275

result:

ok 1 number(s): "586189275"

Test #10:

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

input:

18 994349080
213262526 331559935 331559947 331559968 331560025 331560048 400218054 410224534 5153771...

output:

705352789

result:

ok 1 number(s): "705352789"

Test #11:

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

input:

20 701655768
28047771 62952676 75073156 86201344 133475866 162185399 187460646 230062409 239115128 2...

output:

0

result:

ok 1 number(s): "0"

Test #12:

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

input:

14 895037836
15992696 80824499 107723002 270918867 289236415 317740651 355172994 355173061 355173062...

output:

4516602

result:

ok 1 number(s): "4516602"

Test #13:

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

input:

17 681068804
3333099 6569576 35334788 75774095 77007954 135512203 139146717 188829256 219916934 2256...

output:

0

result:

ok 1 number(s): "0"

Test #14:

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

input:

14 986544022
9208421 68182272 181134488 274863798 276971587 457978810 717926835 744809821 842948107 ...

output:

530761723

result:

ok 1 number(s): "530761723"

Test #15:

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

input:

18 686946272
17650954 248721992 285190081 327365119 368130513 379494732 380371231 399949596 45656616...

output:

849349982

result:

ok 1 number(s): "849349982"

Test #16:

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

input:

20 881666186
1618978 5555321 71528763 96237665 109539826 115510796 138365126 141133644 144599796 168...

output:

922470100

result:

ok 1 number(s): "922470100"

Test #17:

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

input:

19 841694692
63833815 69282153 91101610 112124586 112554825 121341401 180063013 184990237 208347789 ...

output:

912979133

result:

ok 1 number(s): "912979133"

Test #18:

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

input:

19 156685182
1423858 2812022 4470024 7637015 13124786 17997660 20589037 41733384 68580641 90312843 1...

output:

610015874

result:

ok 1 number(s): "610015874"

Test #19:

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

input:

19 702377626
4767885 33054077 44059163 67140541 104963922 163237651 181005251 415323229 437648551 49...

output:

597679143

result:

ok 1 number(s): "597679143"

Subtask #2:

score: 20
Accepted

Test #20:

score: 20
Accepted
time: 0ms
memory: 1204kb

input:

37 1000000000
12166968 17806149 27392015 55579701 143347943 181454312 184278770 220511349 248812352 ...

output:

208130147

result:

ok 1 number(s): "208130147"

Test #21:

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

input:

39 948719387
20285451 61467668 74070870 100327540 147542392 149514032 193585024 254505553 260569486 ...

output:

4969584

result:

ok 1 number(s): "4969584"

Test #22:

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

input:

40 669143496
13333708 40519682 51234511 123203209 127811611 144889911 150791763 157948449 161006777 ...

output:

233694548

result:

ok 1 number(s): "233694548"

Test #23:

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

input:

40 8006626
41392 243672 411059 453619 677910 861327 1004888 1254008 1673001 1851283 2091402 2117921 ...

output:

587636335

result:

ok 1 number(s): "587636335"

Test #24:

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

input:

40 734503052
12642237 24098065 51260789 51910984 94005453 118214482 134886502 149439398 186677929 18...

output:

722137528

result:

ok 1 number(s): "722137528"

Test #25:

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

input:

40 632336988
20448777 21003492 28382926 32394921 60599261 80279148 142620834 169177323 205297226 206...

output:

711938591

result:

ok 1 number(s): "711938591"

Test #26:

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

input:

40 882308160
8207206 19993339 67906737 70919740 127966077 179570444 207391309 208942444 217564631 22...

output:

389750251

result:

ok 1 number(s): "389750251"

Test #27:

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

input:

40 186607324
7040229 13294811 15333062 15515912 17280143 27306414 34516874 34846853 40638496 4063850...

output:

705612475

result:

ok 1 number(s): "705612475"

Test #28:

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

input:

40 589773978
10567221 19802517 163445023 170020943 170944845 201832696 201832713 201832725 201832729...

output:

190340554

result:

ok 1 number(s): "190340554"

Test #29:

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

input:

39 165164160
1506492 1539702 4161982 8169502 14964329 16476793 17140786 17278497 18658813 19548396 2...

output:

0

result:

ok 1 number(s): "0"

Test #30:

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

input:

40 518080566
5129759 5932894 19759553 26748485 29566134 34826067 38335147 57244915 76484698 83090991...

output:

101313479

result:

ok 1 number(s): "101313479"

Test #31:

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

input:

40 597580328
283496035 283496063 283496103 283496297 283496300 283496336 283496373 283496375 2834964...

output:

648026391

result:

ok 1 number(s): "648026391"

Test #32:

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

input:

38 920207808
24751774 72785225 90819594 93607259 100699980 101796718 114019933 131593627 619197675 6...

output:

0

result:

ok 1 number(s): "0"

Test #33:

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

input:

40 381115838
11023671 31498198 36532159 38945095 40605004 46531043 46565559 47723559 52104993 551009...

output:

260034140

result:

ok 1 number(s): "260034140"

Test #34:

score: 0
Accepted
time: 2ms
memory: 1208kb

input:

39 598628540
14521990 28472343 50958159 126362154 126760671 139573888 151780407 179463789 179693727 ...

output:

332906193

result:

ok 1 number(s): "332906193"

Test #35:

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

input:

40 625217532
18748303 19652013 32997590 37083056 43921422 49375204 67731727 79128314 86875363 178550...

output:

953693985

result:

ok 1 number(s): "953693985"

Test #36:

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

input:

39 926448348
65833155 99654197 116210614 119706869 150518734 180839765 248446088 313535477 332432065...

output:

281629544

result:

ok 1 number(s): "281629544"

Test #37:

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

input:

38 487732324
13447058 70026613 81680427 98662542 120791911 154334980 162320271 186180041 230185904 2...

output:

919035670

result:

ok 1 number(s): "919035670"

Test #38:

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

input:

31 568574992
3000700 14528616 31462265 35691823 37861234 40763033 48010238 58236319 74453129 8436058...

output:

67737808

result:

ok 1 number(s): "67737808"

Subtask #3:

score: 30
Accepted

Test #39:

score: 30
Accepted
time: 3ms
memory: 1268kb

input:

2000 1000000000
943353 1675978 1713005 3044694 3238414 3771110 3868411 3873418 3984595 4141387 42943...

output:

510215858

result:

ok 1 number(s): "510215858"

Test #40:

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

input:

2000 1000000000
234133 1427937 1439048 2182363 2441904 2716896 3121815 3559153 3655946 4505348 46238...

output:

189522573

result:

ok 1 number(s): "189522573"

Test #41:

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

input:

2000 1000000000
925775 1612108 1754325 1873611 2477266 2580560 2894149 2926797 3013074 3516900 48740...

output:

951380663

result:

ok 1 number(s): "951380663"

Test #42:

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

input:

2000 1000000000
555774 857120 1530936 1944835 2364330 2987811 3839013 4037550 4158697 4165400 447210...

output:

794610113

result:

ok 1 number(s): "794610113"

Test #43:

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

input:

2000 1000000000
478646 3609755 5597111 5857442 6045704 7237806 7438395 7472395 8294238 8382277 84517...

output:

984962247

result:

ok 1 number(s): "984962247"

Subtask #4:

score: 30
Accepted

Test #44:

score: 30
Accepted
time: 552ms
memory: 32456kb

input:

999973 1000000000
282 400 579 1551 3434 3497 4963 5368 5967 6174 6467 6573 7797 9748 10141 12804 129...

output:

993435258

result:

ok 1 number(s): "993435258"

Test #45:

score: 0
Accepted
time: 462ms
memory: 32452kb

input:

999999 688206363
684 1448 2139 3549 5208 5366 6860 6866 6927 7080 7384 8060 11629 11962 12426 12605 ...

output:

924991711

result:

ok 1 number(s): "924991711"

Test #46:

score: 0
Accepted
time: 746ms
memory: 32452kb

input:

999990 877587226
2359 2734 2810 3717 4332 5094 5606 5670 6864 7768 9986 10769 12004 12476 12613 1691...

output:

390428229

result:

ok 1 number(s): "390428229"

Test #47:

score: 0
Accepted
time: 421ms
memory: 32456kb

input:

999939 264914790
27 283 289 563 604 1142 2164 2400 2916 3190 3364 3447 3598 4325 4853 5164 5381 5611...

output:

972015007

result:

ok 1 number(s): "972015007"

Test #48:

score: 0
Accepted
time: 418ms
memory: 32456kb

input:

999994 218737008
144 147 284 332 585 952 1107 1314 1363 1565 2404 2464 3309 3548 3602 3778 4007 4219...

output:

288664595

result:

ok 1 number(s): "288664595"

Test #49:

score: 0
Accepted
time: 406ms
memory: 32452kb

input:

999979 466355172
643 677 826 2266 2661 3603 3734 3846 4160 4229 4326 4612 5260 5815 5849 7013 7320 7...

output:

486535243

result:

ok 1 number(s): "486535243"

Test #50:

score: 0
Accepted
time: 450ms
memory: 32452kb

input:

999997 768994640
1029 1115 2332 3356 3760 3858 5815 5963 6214 7585 7640 8565 9675 10693 10796 11958 ...

output:

731051816

result:

ok 1 number(s): "731051816"

Test #51:

score: 0
Accepted
time: 370ms
memory: 32452kb

input:

999972 545641084
125456840 125456857 125456922 125456979 125456986 125457077 125457109 125457111 125...

output:

765575848

result:

ok 1 number(s): "765575848"

Test #52:

score: 0
Accepted
time: 412ms
memory: 32456kb

input:

999995 754093274
172 2104 11192 16901 17095 24705 34527 37379 39195 40795 47118 50222 51735 55402 58...

output:

65531123

result:

ok 1 number(s): "65531123"

Test #53:

score: 0
Accepted
time: 341ms
memory: 32456kb

input:

999965 101779236
2625020 2625033 2625103 2625385 2625418 2625545 2625740 2625764 2625797 2625834 262...

output:

748181579

result:

ok 1 number(s): "748181579"

Test #54:

score: 0
Accepted
time: 414ms
memory: 32452kb

input:

999998 37653022
22 46 120 176 192 235 265 268 283 301 340 377 378 382 383 427 434 437 463 508 526 56...

output:

847421020

result:

ok 1 number(s): "847421020"

Test #55:

score: 0
Accepted
time: 421ms
memory: 32456kb

input:

999992 420373896
302 400 742 836 1212 1550 2993 5840 6546 6824 6877 7469 7698 8139 8407 8411 8420 87...

output:

178425934

result:

ok 1 number(s): "178425934"

Test #56:

score: 0
Accepted
time: 76ms
memory: 8952kb

input:

999936 25311270
24 34 44 59 65 66 77 87 104 122 153 179 190 242 244 248 265 282 291 292 293 296 299 ...

output:

0

result:

ok 1 number(s): "0"

Test #57:

score: 0
Accepted
time: 444ms
memory: 32452kb

input:

999997 754066830
549 713 1281 2441 2877 3748 3904 3912 4665 4982 5346 5637 5765 6302 7164 7741 9901 ...

output:

220912795

result:

ok 1 number(s): "220912795"

Test #58:

score: 0
Accepted
time: 433ms
memory: 32456kb

input:

999943 464478556
3682 4648 12316 16649 17238 21913 23834 28854 37639 44995 47087 47896 50025 51091 5...

output:

378521263

result:

ok 1 number(s): "378521263"

Test #59:

score: 0
Accepted
time: 811ms
memory: 32452kb

input:

999973 488919610
3293 5245 19864 21181 45331 47751 51087 60789 61338 95937 102599 114765 133977 1367...

output:

840151413

result:

ok 1 number(s): "840151413"

Test #60:

score: 0
Accepted
time: 419ms
memory: 32456kb

input:

999995 536282820
118 130 1026 1051 1376 1427 1847 1858 2000 2048 2158 2385 2681 2793 2808 2859 2894 ...

output:

218495090

result:

ok 1 number(s): "218495090"

Test #61:

score: 0
Accepted
time: 775ms
memory: 32456kb

input:

999999 575711746
53 5260 52710 120447 164269 186027 197794 208334 293089 310856 323053 337444 356071...

output:

878654218

result:

ok 1 number(s): "878654218"

Test #62:

score: 0
Accepted
time: 574ms
memory: 32456kb

input:

1000000 504893482
190 311 1045 1832 2317 3345 3416 3445 3524 3710 3807 4089 4374 4438 5089 5094 5161...

output:

808690555

result:

ok 1 number(s): "808690555"

Test #63:

score: 0
Accepted
time: 364ms
memory: 32456kb

input:

999957 77807572
7461772 7461773 7461779 7461780 7461781 7461782 7461788 7461792 7461793 7461799 7461...

output:

603586278

result:

ok 1 number(s): "603586278"

Test #64:

score: 0
Accepted
time: 392ms
memory: 32452kb

input:

999972 398782100
84824939 84824968 84824987 84825031 84825078 84825123 84825125 84825133 84825135 84...

output:

344069802

result:

ok 1 number(s): "344069802"

Extra Test:

score: 0
Extra Test Passed