QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#556960 | #8556. Somewhere Over the Rainbow | hhoppitree | RE | 0ms | 0kb | C++17 | 1.1kb | 2024-09-10 22:46:44 | 2024-09-10 22:46:46 |
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