QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#546646 | #8556. Somewhere Over the Rainbow | Made_in_Code | WA | 1ms | 5768kb | C++14 | 1.7kb | 2024-09-04 11:05:30 | 2024-09-04 11:05:30 |
Judging History
answer
#include <iostream>
#include <queue>
#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) * (a[y].y - a[o].y) -
(LLL)(a[y].x - a[o].x) * (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 = (LD)dy / dx - (LD)(dx - 1) / 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++) {
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 * 3 - dx) % kMod * kInv3) % kMod;
LL d = (dx * kr + 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: 5768kb
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: 5640kb
input:
0 5
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 5636kb
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:
9475
result:
wrong answer 1st numbers differ - expected: '10725', found: '9475'