QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#556960#8556. Somewhere Over the RainbowhhoppitreeRE 0ms0kbC++171.1kb2024-09-10 22:46:442024-09-10 22:46:46

Judging History

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

  • [2024-09-10 22:46:46]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-09-10 22:46:44]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

vector< tuple<int, long long, long long, __int128> > S;

__int128 f(long long x, long long y) {
    __int128 n = y - x + 1;
    return x * n * (n + 1) - n * (n + 1) / 2 * (x + n) + n * (n + 1) * (n + n + 1) / 6;
}

void ins(int a, long long b) {
    auto [x, y, z, w] = S.back();
    __int128 sy = (__int128)y * (a - x) - (__int128)(a - x) * (a - x + 1) / 2;
    if (sy < b) {
        S.pop_back(), ins(a, b);
        return;
    }
    __int128 D = sy - b, o = D / (a - x), re = D % (a - x), l = z - (a - x) - o, s = y * (a - x) + f(l + (a - x) - 1, l);
    s -= re * (re + 1) / 2;
    S.push_back({a, b, l - (re != 0), s});
}

signed main() {
    int n, m; scanf("%d%d", &n, &m);
    S.push_back({0, 0, 1e18, 0});
    for (int i = 1; i <= n; ++i) {
        int x; long long y;
        scanf("%d%lld", &x, &y);
        ins(x, y);
    }
    ins(m, 0);
    __int128 res = 0;
    for (auto [x, y, z, w] : S) res += w;
    printf("%d\n", (int)(res % 998244353));
    return 0;
}

詳細信息

Test #1:

score: 0
Runtime Error

input:

3 6
1 100
4 42
5 22

output:


result: