ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#173082 | #3151. Convex Hull | li0201 | 100 | 9721ms | 32456kb | C++11 | 3.2kb | 2023-07-11 11:51:02 | 2023-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