QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#546865#8556. Somewhere Over the RainbowMade_in_CodeAC ✓38ms10740kbC++141.7kb2024-09-04 15:01:172024-09-04 15:01:17

Judging History

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

  • [2024-09-04 15:01:17]
  • 评测
  • 测评结果:AC
  • 用时:38ms
  • 内存:10740kb
  • [2024-09-04 15:01:17]
  • 提交

answer

#include <iostream>
#define LL long long
#define LLL __int128_t

using namespace std;

const LL kMaxN = 2e5 + 3, kInf = 2e18, kMod = 998244353, kInv3 = 332748118;
struct A {
  LL x, y;
} a[kMaxN];
struct Q {
  int x;
  LL k;
} q[kMaxN];
int n, m, h, t, l[kMaxN];
LL ans;

LLL Cross(int o, int x, int y) {
  return (LLL)(a[x].x - a[o].x) * (LLL)(a[y].y - a[o].y) -
         (LLL)(a[y].x - a[o].x) * (LLL)(a[x].y - a[o].y);
}

int main() {
  cin.tie(0), cout.tie(0);
  ios::sync_with_stdio(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i].x >> a[i].y;
  }
  t = 1, a[++n] = {m, 0};
  for (int i = 0; i <= n; i++) {
    for (; h > 1 && Cross(l[h - 1], l[h], i) >= 0; h--) {
    }
    l[++h] = i;
  }
  for (int i = 2; i <= h; i++) {
    int x = l[i];
    for (;; t--) {
      LL dx = a[x].x - a[q[t].x].x, dy = a[x].y - a[q[t].x].y;
      LL kl, kr;
      if (dy >= dx * (dx - 1) / 2) {
        kr = (dy - dx * (dx - 1) / 2) / dx;
      } else {
        kr = (dy - dx * (dx + 1) / 2 + 1) / dx;
      }
      kl = kr + dx;
      if ((LLL)dx * (LLL)kr + dx * (dx - 1) / 2 == dy) {
        kl--;
      }
      if (t == 1 || q[t].k > kl) {
        q[++t] = {x, kr};
        break;
      }
    }
  }
  for (int i = 2; i <= t; i++) {
    LL dx = (a[q[i].x].x - a[q[i - 1].x].x) % kMod;
    LL dy = (a[q[i].x].y - a[q[i - 1].x].y) % kMod;
    LL k = q[i].k % kMod;
    ans = (ans + a[q[i].x].y % kMod * dx) % kMod;
    ans = (ans - k * (dx - 1) % kMod * (dx - 1)) % kMod;
    ans = (ans + (dx - 2) * (dx - 1) / 2 % kMod * (k * 3 - dx) % kMod * kInv3) % kMod;
    LL d = (k * dx + dx * (dx - 1) / 2 - dy) % kMod;
    ans = (ans - d * (d + 1) / 2) % kMod;
  }
  cout << (ans + kMod) % kMod << '\n';
  return 0;
}

詳細信息

Test #1:

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

input:

3 6
1 100
4 42
5 22

output:

310

result:

ok 1 number(s): "310"

Test #2:

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

input:

0 5

output:

10

result:

ok 1 number(s): "10"

Test #3:

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

input:

20 50
4 11
7 4
8 20
13 9
14 29
15 26
16 19
18 18
29 46
30 7
34 37
35 16
38 14
39 47
40 18
42 30
43 6
44 23
47 13
48 4

output:

10725

result:

ok 1 number(s): "10725"

Test #4:

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

input:

40 100
3 20
4 67
5 62
7 75
9 49
11 14
14 31
18 11
19 5
24 98
25 100
28 35
30 19
31 20
32 71
37 29
38 5
40 94
45 95
46 65
51 2
52 52
53 61
54 77
57 50
59 69
61 30
65 50
67 4
68 56
73 99
75 15
76 47
78 52
79 72
83 91
88 44
89 3
91 55
94 2

output:

84575

result:

ok 1 number(s): "84575"

Test #5:

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

input:

60 150
1 119
4 135
5 75
9 13
11 72
15 34
17 130
21 12
26 107
30 133
33 18
34 135
36 78
37 95
38 26
42 24
44 25
51 49
52 73
54 40
55 100
56 67
61 128
62 87
74 131
75 103
77 84
78 37
81 51
82 83
83 89
84 58
89 117
93 148
94 127
95 118
96 103
97 49
98 28
99 83
102 65
105 97
107 103
109 9
113 40
116 107...

output:

286360

result:

ok 1 number(s): "286360"

Test #6:

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

input:

80 200
3 165
5 49
10 42
11 7
12 115
13 78
14 52
15 102
17 132
18 181
19 36
21 59
23 139
24 8
25 54
26 181
29 178
33 120
37 163
38 90
41 182
44 133
48 171
50 60
52 74
53 174
58 156
61 65
64 156
66 174
67 24
70 64
73 57
77 179
80 5
84 38
86 152
90 153
94 137
96 24
99 59
101 180
103 156
109 29
111 55
1...

output:

674709

result:

ok 1 number(s): "674709"

Test #7:

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

input:

100 250
1 99
2 176
4 122
5 16
6 138
7 59
9 134
10 185
11 249
12 245
13 148
14 9
15 74
20 190
23 203
24 239
31 41
32 202
33 155
37 26
40 170
43 84
45 144
46 59
47 169
54 184
56 37
57 106
58 38
60 219
63 40
66 245
68 106
70 97
72 127
74 146
75 1
76 173
77 179
79 205
81 72
83 90
85 17
88 227
90 163
92 ...

output:

1309875

result:

ok 1 number(s): "1309875"

Test #8:

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

input:

120 300
5 37
6 246
13 248
14 152
15 250
16 221
17 201
20 171
21 73
23 97
24 163
26 168
28 228
29 57
31 193
32 226
34 7
35 81
39 78
41 120
42 290
44 228
47 192
49 269
50 86
52 222
54 91
55 37
59 94
61 24
62 200
65 221
68 119
72 230
75 20
76 160
77 288
81 32
84 84
85 19
88 22
94 240
98 135
99 284
102 ...

output:

2261225

result:

ok 1 number(s): "2261225"

Test #9:

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

input:

140 350
1 82
3 115
4 59
7 212
9 307
10 149
18 189
19 43
21 77
22 264
25 177
29 117
31 49
32 181
33 231
34 45
35 152
41 314
42 258
43 276
44 33
45 114
48 119
49 323
59 100
60 26
61 40
63 304
64 343
65 277
67 138
74 234
78 188
79 59
80 213
81 257
83 197
84 76
94 286
96 72
97 225
98 14
101 154
102 202
...

output:

3588200

result:

ok 1 number(s): "3588200"

Test #10:

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

input:

160 400
3 76
4 29
7 25
16 73
18 76
19 368
21 311
23 111
25 298
26 51
28 396
29 11
31 213
32 284
35 395
36 214
37 256
40 216
41 178
44 101
46 382
47 286
49 64
52 184
56 113
57 247
59 308
64 393
66 392
67 46
68 256
69 230
76 153
78 263
80 396
84 9
87 3
93 373
94 35
95 48
97 305
98 310
105 2
106 94
109...

output:

5353300

result:

ok 1 number(s): "5353300"

Test #11:

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

input:

180 450
6 384
9 255
10 135
11 389
12 355
13 170
14 87
15 355
16 295
17 397
19 244
20 238
22 61
28 346
31 411
32 315
34 220
36 133
38 47
41 21
42 99
43 354
44 212
45 368
50 85
52 99
55 147
58 119
59 24
66 349
67 103
69 77
73 97
76 339
77 417
80 175
82 343
88 265
90 184
91 225
92 269
93 301
94 35
95 2...

output:

7619025

result:

ok 1 number(s): "7619025"

Test #12:

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

input:

200 500
2 302
4 37
14 133
16 148
18 138
19 61
21 206
24 361
25 417
26 171
27 70
29 314
30 43
31 231
34 341
37 373
39 144
43 371
44 239
46 494
49 159
51 18
53 163
56 167
57 446
60 215
62 381
63 116
64 37
67 382
69 375
71 331
77 125
79 432
81 256
83 130
84 333
86 264
89 31
91 27
93 340
94 366
95 315
9...

output:

10447875

result:

ok 1 number(s): "10447875"

Test #13:

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

input:

123748 1237481
10 3247552102
14 4546572905
15 4871328114
18 5845593708
29 9417900801
31 10067411175
34 11041676717
37 12015942260
50 16237759481
58 18835800760
67 21758597131
72 23382372855
73 23707127994
78 25330903696
86 27928944751
90 29227965263
129 41893414353
132 42867679610
142 46115230387
15...

output:

710395341

result:

ok 1 number(s): "710395341"

Test #14:

score: 0
Accepted
time: 36ms
memory: 10652kb

input:

199243 42347811
64 4603886408874124
195 4679686730221000
254 4693712705024254
851 4753728283824726
1655 4834553283856499
1658 4834854869676312
1897 4857473144231115
2204 4886526743679897
2371 4902331144643413
2809 4920779628345774
3408 4946009403692092
3905 4966942956586712
4027 4966980057441786
416...

output:

214677153

result:

ok 1 number(s): "214677153"

Test #15:

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

input:

2 1000000000
1 1000000000000000000
999999999 1000000000000000000

output:

990076733

result:

ok 1 number(s): "990076733"

Test #16:

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

input:

0 1000000000

output:

817114508

result:

ok 1 number(s): "817114508"

Test #17:

score: 0
Accepted
time: 17ms
memory: 5712kb

input:

100000 1000000000
1720 545129961903939062
2828 68944037491821017
22642 765357885440953113
31553 804195988082110897
42148 451982057873380762
75271 738379011585444789
82853 720718852602835649
82947 247713776500380751
83382 705355905061929496
92028 91339498972704298
97921 84401824226446199
111716 71400...

output:

190785398

result:

ok 1 number(s): "190785398"

Test #18:

score: 0
Accepted
time: 31ms
memory: 10648kb

input:

200000 1000000000
6528 837941191104684962
10362 551600581191408331
13986 82449114129176619
18076 48316138635032354
24093 694117401705053967
26723 215913962974932772
29282 338322765800166787
36619 731170060169182885
47690 61718601621883429
50218 520831739296403423
51373 335686593594519563
52624 69769...

output:

332201468

result:

ok 1 number(s): "332201468"

Test #19:

score: 0
Accepted
time: 32ms
memory: 10612kb

input:

200000 1000000000
62 1773013655269235
1003 28682785422674067
2669 76325378156417883
3022 86420117192683117
8446 241530215003368983
19847 567564548450898948
22092 581046536788825107
29786 627251622840564522
31296 628187733094315622
34564 630213698854227403
44253 631541805100186193
47740 6320197807692...

output:

207885978

result:

ok 1 number(s): "207885978"

Test #20:

score: 0
Accepted
time: 37ms
memory: 10544kb

input:

200000 1000000000
4517 219261183621493509
5477 265860859571185514
10669 517887440316465765
13644 545000585461842264
18953 593385018238776481
24167 640903653076461771
27625 672418697033220048
28470 680119741607301610
33788 719637397799400751
37138 744530994671593430
37367 746232676367820085
38038 751...

output:

20899995

result:

ok 1 number(s): "20899995"

Test #21:

score: 0
Accepted
time: 37ms
memory: 10432kb

input:

200000 1000000000
5439 20514748114501759
6275 23667961831997117
29024 109472338189682530
29315 110168967752593189
41866 140215007686062721
48719 146469163763700033
51387 148485368550868986
57791 153324864570182503
58170 153611274467604153
61098 155823960952605967
62725 157053483117991306
66899 16020...

output:

466849106

result:

ok 1 number(s): "466849106"

Test #22:

score: 0
Accepted
time: 33ms
memory: 10664kb

input:

200000 1000000000
5634 377638099628411719
23462 591813284240386278
31819 623666216721399274
33898 629938128773416938
34630 631463611188571234
39657 632180968325090555
44425 632861365919985587
54592 634312205262540124
59774 634531055832997026
61049 634584902698300332
64629 634736096240812885
67615 63...

output:

925728708

result:

ok 1 number(s): "925728708"

Test #23:

score: 0
Accepted
time: 34ms
memory: 10568kb

input:

200000 1000000000
11687 944358982930984733
11982 960515125757551249
17427 962286508308029607
26725 965311359470774590
31691 966926912336431665
32819 967293876415246196
50217 972953841717931813
62472 976940671906633230
65252 976947205132081834
66848 976950955858019810
69281 976954087157118480
70868 9...

output:

256530591

result:

ok 1 number(s): "256530591"

Test #24:

score: 0
Accepted
time: 37ms
memory: 10660kb

input:

200000 1000000000
7721 411355329653835140
8451 450247881217554891
14297 539051829553285621
15290 545022457465904654
19677 571400246630998006
27065 585471912753453829
34162 598989321266083603
39237 600714080097293320
45979 602078974566453279
47793 602446212554399921
55712 604049386510646452
57563 604...

output:

284644857

result:

ok 1 number(s): "284644857"

Test #25:

score: 0
Accepted
time: 30ms
memory: 10584kb

input:

200000 1000000000
5297 161985813130235837
5923 181129313037675435
7815 238987942148513399
21757 665343654016615592
24285 742651589701044218
25439 744053451131722337
25718 744196248219918069
31223 746458260009633947
35672 748138801892991209
49017 752746679560573518
51058 753130801578356039
55475 7537...

output:

434088400

result:

ok 1 number(s): "434088400"

Test #26:

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

input:

200000 1000000000
1918 876657951154237156
7349 896443460249678281
9464 904148551704936659
16734 907594660905811873
24625 907922042499879946
25037 907939135542999802
31367 908171665389820163
31444 908173462822447518
48731 908296575208800759
50511 908307831595544701
66997 908412085822425870
81669 9084...

output:

860866989

result:

ok 1 number(s): "860866989"

Test #27:

score: 0
Accepted
time: 26ms
memory: 10580kb

input:

200000 1000000000
3317 438592489717299576
10379 711939767663099278
13363 792639292733990448
28456 994600571323429637
35428 999318767276199412
40219 999634601671730364
40748 999667480720331684
40873 999669939471656133
41204 999675056384009450
42698 999695201649937368
43352 999696627724953084
48731 99...

output:

688001246

result:

ok 1 number(s): "688001246"

Test #28:

score: 0
Accepted
time: 30ms
memory: 10720kb

input:

200000 1000000000
1157 534522213512822094
6007 730770171039516291
12416 935704700959329405
14167 982505703935879148
17612 997062828852344060
59185 997296281363294542
69241 997347736885195062
77338 997344053895944902
78106 997343678616490884
82343 997341607100009704
83670 997340957917183620
84807 997...

output:

767554487

result:

ok 1 number(s): "767554487"

Test #29:

score: 0
Accepted
time: 30ms
memory: 7632kb

input:

200000 1000000000
921 1914462257475
12450 25879466891768
14664 30481630554171
17194 35740646262987
19289 40095439011178
33196 69003252681126
37783 78537987090049
40628 84451715212909
50863 105726519044875
60667 126105334029970
73046 151836464649605
85960 178679489055613
87544 181971978011413
98150 2...

output:

160461773

result:

ok 1 number(s): "160461773"

Test #30:

score: 0
Accepted
time: 35ms
memory: 7644kb

input:

200000 1000000000
5553 311287337276132
7581 424971954115567
12926 724599289937231
15835 887670544518368
16615 931395389615675
27142 1521512566433820
30665 1719003072123654
34673 1943681441023817
35168 1971429891158215
47909 2685658096055357
48684 2729102628828682
52346 2934385045241208
55504 3111414...

output:

706303364

result:

ok 1 number(s): "706303364"

Test #31:

score: 0
Accepted
time: 35ms
memory: 8412kb

input:

200000 1000000000
1895 1080347168360057
2869 1635628508378525
4630 2639581729556112
8459 4822510102663808
26099 14879145197094066
29942 17070054944243938
31519 17969108978808503
32928 18772385536439468
41998 23943228908159837
48086 27414022075583794
49062 27970443578609252
50892 29013733894214505
53...

output:

781041678

result:

ok 1 number(s): "781041678"

Test #32:

score: 0
Accepted
time: 37ms
memory: 10644kb

input:

200000 1000000000
1728 256118639011086137
4430 356456728677792517
7549 361971082380962795
12661 364803035519911492
14800 365220541887229577
19927 365677273047248973
20676 365734670396148810
24349 365903904470992375
28219 365915674572531154
29786 365918642018776381
37168 365920130674154721
47678 3659...

output:

120167879

result:

ok 1 number(s): "120167879"