QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#546675#8556. Somewhere Over the RainbowMade_in_CodeWA 38ms12184kbC++141.7kb2024-09-04 11:31:042024-09-04 11:31:06

Judging History

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

  • [2024-09-04 11:31:06]
  • 评测
  • 测评结果:WA
  • 用时:38ms
  • 内存:12184kb
  • [2024-09-04 11:31:04]
  • 提交

answer

#include <assert.h>

#include <cmath>
#include <iostream>
#define LL long long
#define LD long double
#define LLL __int128_t

using namespace std;

const LL kMaxN = 2e5 + 1, kInf = 2e18, kMod = 998244353, kInv3 = 332748118;
struct A {
  LL x, y;
} a[kMaxN];
struct Q {
  int x;
  LL l, r;
} 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;
  }
  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;
  }
  q[t = 1] = {0, kInf, kInf};
  for (int i = 2; i <= h; i++) {
    int x = l[i];
    for (; t; t--) {
      LL dx = a[x].x - a[q[t].x].x, dy = a[x].y - a[q[t].x].y;
      LL kr = floor((LD)dy / dx - (LD)(dx - 1) / 2), kl = kr + dx;
      assert((LLL)dx * (LLL)kr < kInf);
      if (dx * kr + dx * (dx - 1) / 2 == dy) {
        kl--;
      }
      if (q[t].r > kl) {
        q[++t] = {x, kl, kr};
        break;
      }
    }
  }
  for (int i = 2; i <= t; i++) {
    LL dx = a[q[i].x].x - a[q[i - 1].x].x, dy = a[q[i].x].y - a[q[i - 1].x].y;
    LL kl = q[i].l, kr = q[i].r;
    ans = (ans + a[q[i].x].y % kMod * dx) % kMod;
    ans = (ans - kr % kMod * (dx - 1) % kMod * (dx - 1)) % kMod;
    ans = (ans + (dx - 2) * (dx - 1) / 2 % kMod * (kr % kMod * 3 - dx) % kMod * kInv3) % kMod;
    LL d = (kr % kMod * dx + dx * (dx - 1) / 2 - dy) % kMod;
    ans = (ans - d * (d + 1) / 2) % kMod;
  }
  cout << (ans + kMod) % kMod << '\n';
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 6
1 100
4 42
5 22

output:

310

result:

ok 1 number(s): "310"

Test #2:

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

input:

0 5

output:

10

result:

ok 1 number(s): "10"

Test #3:

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

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: 1ms
memory: 5704kb

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: 0ms
memory: 5648kb

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: 5652kb

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: 0ms
memory: 7828kb

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: 5704kb

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: 5648kb

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: 5648kb

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: 0ms
memory: 5732kb

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: 5708kb

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: 20ms
memory: 8560kb

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: 37ms
memory: 12184kb

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: 1ms
memory: 5648kb

input:

2 1000000000
1 1000000000000000000
999999999 1000000000000000000

output:

990076733

result:

ok 1 number(s): "990076733"

Test #16:

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

input:

0 1000000000

output:

817114508

result:

ok 1 number(s): "817114508"

Test #17:

score: 0
Accepted
time: 10ms
memory: 7828kb

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: 33ms
memory: 8500kb

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: -100
Wrong Answer
time: 38ms
memory: 10144kb

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:

351482259

result:

wrong answer 1st numbers differ - expected: '207885978', found: '351482259'