QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#546668 | #8556. Somewhere Over the Rainbow | Made_in_Code | WA | 0ms | 5696kb | C++14 | 1.7kb | 2024-09-04 11:25:07 | 2024-09-04 11:25:08 |
Judging History
answer
#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) * (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;
cout << '(' << a[i].x << ',' << a[i].y << ")\n";
}
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;
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: 0
Wrong Answer
time: 0ms
memory: 5696kb
input:
3 6 1 100 4 42 5 22
output:
(1,100) (4,42) (5,22) 310
result:
wrong output format Expected integer, but "(1,100)" found