50pts, 加速和平速有点问题,注释是豆包写的

#include<bits/stdc++.h>
#define int long long  // 定义int为long long，避免整数溢出
using namespace std;

const int N = 1e5 + 5;  // 数组最大长度，适应题目中1e5的数量级
int T;  // 测试数据组数

// 存储车辆信息的结构体
struct node {
    int d, v, a;  // d:驶入位置，v:初速度，a:加速度
    double l, r;  // 超速区间的左右端点（位置）
    bool vis;     // 标记车辆是否超速及类型（0:不超速，1/2/3:不同类型的超速）
} c[N];

// 存储超速车辆对应测速仪索引区间的结构体
struct node2 {
    int l, r;  // 测速仪索引的区间[左,右]
    // 排序运算符重载：按右端点升序，右端点相同时按左端点升序
    bool friend operator < (node2 a, node2 b) {
        if(a.r != b.r)
            return a.r < b.r;
        return a.l < b.l;
    }
} k[N];

int p[N];  // 存储测速仪位置（已排序）

void solve() {
    int tot = 0;  // 记录超速车辆的数量（用于第二问）
    // 初始化数组（实际可省略，因每次都会重新赋值）
    memset(c, 0, sizeof(c));
    memset(k, 0, sizeof(k));
    memset(p, 0, sizeof(p));
    
    int n, m, L, V;  // n:车辆数，m:测速仪数，L:主干道长度，V:限速
    cin >> n >> m >> L >> V;
    
    // 读入n辆车的信息
    for(int i = 1; i <= n; i++)
        cin >> c[i].d >> c[i].v >> c[i].a;
    
    // 读入m个测速仪的位置（题目保证已按升序排列）
    for(int i = 1; i <= m; i++)
        cin >> p[i];
    
    int ans = 0;  // 第一问答案：所有测速仪开启时超速的车辆数
    int sum = 0;  // 第二问辅助变量：最少需要保留的测速仪数量
    
    // 处理每辆车，判断是否超速
    for(int i = 1; i <= n; i++) {
        int d = c[i].d, v = c[i].v, a = c[i].a;
        
        // 情况1：加速度a < 0（减速运动）
        if(a < 0) {
            // 初速度 <= 限速，不会超速
            if(v <= V)
                continue;
            
            // 计算超速区间左端点：驶入位置d
            c[i].l = d;
            // 计算速度减到V时的位置：s = (V² - v²)/(2a) + d（因a为负，是减速到V的位移）
            c[i].r = double((V * V - v * v * 1.0) / (2.0 * a)) + d;
            
            // 查找第一个 >= 左端点的测速仪位置
            int id = lower_bound(p + 1, p + 1 + m, c[i].l) - p;
            if(id == m + 1)  // 没有符合条件的测速仪，不超速
                continue;
            
            // 若超速区间右端点超过主干道终点L，修正为L
            if(c[i].r > L) {
                c[i].r = L;
                ans++;  // 该车辆超速
                c[i].vis = 2;  // 标记类型2：区间到L结束
            }
            // 否则，若存在测速仪在区间内，该车辆超速
            else if(p[id] < c[i].r) {
                ans++;
                c[i].vis = 1;  // 标记类型1：区间在L内结束
            }
        }
        
        // 情况2：加速度a = 0（匀速运动）
        if(a == 0) {
            // 速度 <= 限速，不会超速
            if(v <= V)
                continue;
            
            // 超速区间：从驶入位置d到主干道终点L
            c[i].l = d;
            c[i].r = L;
            
            // 查找第一个 >= 左端点的测速仪位置
            int id = lower_bound(p + 1, p + 1 + m, c[i].l) - p;
            if(id != m + 1) {  // 存在符合条件的测速仪，该车辆超速
                ans++;
                c[i].vis = 2;  // 标记类型2
            }
        }
        
        // 情况3：加速度a > 0（加速运动）
        if(a > 0) {
            // 初速度 > 限速，全程超速（从d到L）
            if(v > V) {
                c[i].l = d;
                c[i].r = L;
                // 查找第一个 >= 左端点的测速仪位置
                int id = lower_bound(p + 1, p + 1 + m, c[i].l) - p;
                if(id != m + 1) {  // 存在符合条件的测速仪，该车辆超速
                    ans++;
                    c[i].vis = 2;  // 标记类型2
                }
                continue;
            }
            
            // 初速度 <= 限速，计算加速到V时的位移s
            double s = max((double)((V * V - v * v * 1.0) / (2.0 * a)), 0.0);
            // 若加速到V时已超过主干道终点，不会超速
            if(d + s >= L)
                continue;
            
            // 超速区间：从加速到V的位置(d+s)到L
            c[i].l = d + s;
            c[i].r = L;
            
            // 查找第一个 > 左端点的测速仪位置（因左端点处速度等于V，不超速）
            int id = upper_bound(p + 1, p + 1 + m, c[i].l) - p;
            if(id != m + 1) {  // 存在符合条件的测速仪，该车辆超速
                ans++;
                c[i].vis = 3;  // 标记类型3：左端点是加速到V的位置
            }
        }
    }
    
    // 处理第二问：收集所有超速车辆对应的测速仪索引区间
    for(int i = 1; i <= n; i++) {
        if(c[i].vis != 0) {  // 只处理超速车辆
            int id, id2;  // 测速仪索引区间[ id, id2 ]
            
            // 根据车辆超速类型计算区间
            if(c[i].vis == 1) {
                // 类型1：超速区间[l, r)，找>=l且<r的测速仪
                id = lower_bound(p + 1, p + 1 + m, c[i].l) - p;
                id2 = lower_bound(p + 1, p + 1 + m, c[i].r) - p - 1;
            }
            if(c[i].vis == 2) {
                // 类型2：超速区间[l, r]，找>=l且<=r的测速仪
                id = lower_bound(p + 1, p + 1 + m, c[i].l) - p;
                id2 = upper_bound(p + 1, p + 1 + m, c[i].r) - p - 1;
            }
            if(c[i].vis == 3) {
                // 类型3：超速区间(l, r]，找>l且<=r的测速仪
                id = upper_bound(p + 1, p + 1 + m, c[i].l) - p;
                id2 = upper_bound(p + 1, p + 1 + m, c[i].r) - p - 1;
            }
            
            // 存储该区间（仅当有效时）
            if(id <= id2) {
                k[++tot] = {id, id2};
            }
        }
    }
    
    // 若没有超速车辆，所有测速仪都可关闭
    if(tot == 0) {
        cout << ans << ' ' << m << '\n';
        return ;
    }
    
    // 贪心算法：求覆盖所有区间的最少点数（测速仪）
    sort(k + 1, k + 1 + tot);  // 按区间右端点升序排序
    int nr = 0;  // 记录当前选择的测速仪索引
    for(int i = 1; i <= tot; i++) {
        // 若当前区间左端点 > 已选的最右索引，需新选一个测速仪（选当前区间右端点）
        if(k[i].l > nr) {
            sum++;  // 增加保留的测速仪数量
            nr = k[i].r;  // 更新最右索引
        }
    }
    
    // 输出结果：第一问答案，第二问答案（总测速仪数 - 最少保留数）
    cout << ans << ' ' << m - sum << '\n';
}

signed main() {
    // 重定向输入输出（调试时使用）
    // freopen("detect3.in", "r", stdin);
    // freopen("detect.out", "w", stdout);
    
    cin >> T;  // 读入测试组数
    while(T--) {
        solve();  // 处理每组测试数据
    }
}