防线

AcWing-120-防线

分析

⌊​D​​min(x,E)−S​​⌋+1,x≥S。

实现

#include <iostream>
using namespace std;

typedef long long LL;
const int N = 200010;
struct node {
    LL s, e, d;
};
int n;
node a[N];

LL sum (LL pos) {
    LL res = 0;
    for (int i = 1; i <= n; ++ i)
        if (a[i].s <= pos)
            res += (min(a[i].e, pos) - a[i].s) / a[i].d + 1;
    return res;
}
bool check (LL val) {
    return sum(val) % 2 == 1;
}

int main () {
    int T;
    scanf("%d", &T);
    while (T --) {
        scanf("%d", &n);
        LL max_e = 0;
        for (int i = 1; i <= n; ++ i) {
            scanf("%lld%lld%lld", &a[i].s, &a[i].e, &a[i].d);
            max_e = max(max_e, a[i].e);
        }

        LL l = 0, r = max_e + 1; // 无解的情况
        while (l < r) {
            LL mid = l + r >> 1;
            if (check(mid) == true)
                r = mid;
            else
                l = mid + 1;
        }

        if (l == max_e + 1)
            printf("There's no weakness.\n");
        else
            printf("%lld %lld\n", l, sum(l) - sum(l - 1));
    }
    return 0;
}