QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#546646#8556. Somewhere Over the RainbowMade_in_CodeWA 1ms5768kbC++141.7kb2024-09-04 11:05:302024-09-04 11:05:30

Judging History

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

  • [2024-09-04 11:05:30]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5768kb
  • [2024-09-04 11:05:30]
  • 提交

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'