2026icpc西安

总结

H. Hydra

Tag： 扫描线

题意：略

题解

先根据M写出总防御的表达式，然后发现分段函数后利用扫描线处理

#include 
using namespace std;
using ll = long long;
using i128 = __int128;
struct node
{ll l, r;
};
struct node2
{ll p, ty;friend bool operator<(const node2 &x, const node2 &y){return x.p < y.p;}
};
void solve()
{ll n, x, y;cin >> n >> x >> y;vector a(n + 1);vector as;ll maxv = 0;for (int i = 1; i <= n; i++){cin >> a[i].l >> a[i].r;ll u = max(0LL, maxv - a[i].l);maxv = max(maxv, a[i].l + a[i].r);if (u < a[i].r){as.push_back({u, 1});as.push_back({a[i].r, -1});}a[i].l = u;}ll ans = 0LL;sort(as.begin(), as.end());for (int i = 1; i <= n; i++){ans += max(0LL, a[i].r - a[i].l);}ans *= y;i128 preval = ans, val;ll pre = 0, sum = 0;for(int i=0;i> T;while (T--)solve();return 0;
}