QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#546668#8556. Somewhere Over the RainbowMade_in_CodeWA 0ms5696kbC++141.7kb2024-09-04 11:25:072024-09-04 11:25:08

Judging History

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

  • [2024-09-04 11:25:08]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:5696kb
  • [2024-09-04 11:25:07]
  • 提交

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