QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#546696 | #8556. Somewhere Over the Rainbow | Made_in_Code | WA | 41ms | 15844kb | C++14 | 1.9kb | 2024-09-04 11:47:16 | 2024-09-04 11:47:17 |
Judging History
answer
#include <cmath>
#include <iostream>
#define LL long long
#define LLL __int128_t
using namespace std;
const LLL kMaxN = 2e5 + 2, kInf = 5e18, kMod = 998244353, kInv3 = 332748118;
struct A {
LLL x, y;
} a[kMaxN];
struct Q {
int x;
LLL l, r;
} q[kMaxN];
int n, m, h, t, l[kMaxN];
LLL 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++) {
LL x, y;
cin >> x >> y;
a[i].x = x, a[i].y = y;
// 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--) {
LLL dx = a[x].x - a[q[t].x].x, dy = a[x].y - a[q[t].x].y;
LLL kr, kl;
if (dy * 2 >= dx * (dx - 1)) {
kr = (dy * 2 - dx * (dx - 1)) / (dx * 2);
} else {
kr = (dy * 2 - dx * (dx + 1) + 1) / (dx * 2);
}
kl = kr + dx;
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++) {
LLL dx = a[q[i].x].x - a[q[i - 1].x].x, dy = a[q[i].x].y - a[q[i - 1].x].y;
LLL 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;
LLL d = (kr % kMod * dx + dx * (dx - 1) / 2 - dy) % kMod;
ans = (ans - d * (d + 1) / 2) % kMod;
}
LL shit = (ans + kMod) % kMod;
cout << shit << '\n';
// 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: 5916kb
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: 5552kb
input:
0 5
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: 0
Accepted
time: 0ms
memory: 5908kb
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: 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: 5868kb
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: 7712kb
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: 5836kb
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: 5680kb
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: 0ms
memory: 7660kb
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: 7720kb
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: 7712kb
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: 5608kb
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: 21ms
memory: 12056kb
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: 41ms
memory: 15844kb
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: 7720kb
input:
2 1000000000 1 1000000000000000000 999999999 1000000000000000000
output:
990076733
result:
ok 1 number(s): "990076733"
Test #16:
score: 0
Accepted
time: 0ms
memory: 5644kb
input:
0 1000000000
output:
817114508
result:
ok 1 number(s): "817114508"
Test #17:
score: 0
Accepted
time: 18ms
memory: 7672kb
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: 32ms
memory: 10520kb
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: 41ms
memory: 13820kb
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: -100
Wrong Answer
time: 28ms
memory: 13816kb
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:
457262473
result:
wrong answer 1st numbers differ - expected: '20899995', found: '457262473'