20pts求助

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node
{
    int l, r;
    bool friend operator<(node a, node b)
    {
        if (a.l == b.l)
            return a.r > b.r;
        return a.l < b.l;
    }
};
const int N = 1e5 + 5;
int d[N], v[N], a[N];
int p[N];
node dak[N];
bool ex[N];
int gl(int num[], int mxs, int x)
{
    int ll = 1, rr = mxs;
    int ans = mxs + 1;
    while (ll <= rr)
    {
        int mid = (ll + rr) / 2;
        if (num[mid] >= x)
        {
            ans = mid;
            rr = mid - 1;
        }
        else
        {
            ll = mid + 1;
        }
    }
    return ans;
}
int gr(int num[], int mxs, int x)
{
    int ll = 1, rr = mxs;
    int ans = mxs + 1;
    while (ll <= rr)
    {
        int mid = (ll + rr) / 2;
        if (num[mid] > x)
        {
            ans = mid;
            rr = mid - 1;
        }
        else
        {
            ll = mid + 1;
        }
    }
    return ans - 1;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--)
    {
        int n, m, L, V;
        cin >> n >> m >> L >> V;
        for (int i = 1; i <= n; ++i)
            cin >> d[i] >> v[i] >> a[i];
        for (int i = 1; i <= m; ++i)
            cin >> p[i];
        int cnt = 0;
        for (int i = 1; i <= n; ++i)
        {
            double mx;
            if (a[i] >= 0)
            {
                mx = L - d[i];
            }
            else
            {
                mx = min((double)(L - d[i]), ((double)v[i] * ((double)v[i] / (-a[i])) / 2));
            }
            if (a[i] == 0)
            {
                if (v[i] > V)
                {
                    int ll = gl(p, m, d[i]);
                    int rr = gr(p, m, d[i] + mx);
                    if (ll <= rr)
                    {
                        cnt++;
                        dak[cnt].l = ll;
                        dak[cnt].r = rr;
                    }
                }
            }
            else if (a[i] > 0)
            {
                if (v[i] > V)
                {
                    int ll = gl(p, m, d[i]);
                    int rr = gr(p, m, d[i] + mx);
                    if (ll <= rr)
                    {
                        cnt++;
                        dak[cnt].l = ll;
                        dak[cnt].r = rr;
                    }
                }
                else
                {
                    double pos = d[i] + (v[i] * ((V - v[i]) / a[i]) + 0.5 * a[i] * ((V - v[i]) / a[i]) * ((V - v[i]) / a[i]));
                    if (pos <= d[i] + mx)
                    {
                        int lp = pos;
                        int ll = 1, rr = m;
                        int lb = m + 1;
                        while (ll <= rr)
                        {
                            int mid = (ll + rr) / 2;
                            if (p[mid] > lp)
                            {
                                lb = mid;
                                rr = mid - 1;
                            }
                            else
                            {
                                ll = mid + 1;
                            }
                        }
                        int right_L = gr(p, m, d[i] + mx);
                        if (lb <= right_L)
                        {
                            cnt++;
                            dak[cnt].l = lb;
                            dak[cnt].r = right_L;
                        }
                    }
                }
            }
            else
            {
                if (v[i] <= V)
                    continue;
                double pos = d[i] + ((double)(V * V) - (double)(v[i] * v[i])) / (2 * a[i]);
                if (pos < d[i])
                    pos = d[i];
                pos = min(pos, (double)d[i] + mx);
                int ll = gl(p, m, pos);
                int rr = gr(p, m, pos);
                if (ll <= rr)
                {
                    cnt++;
                    dak[cnt].l = ll;
                    dak[cnt].r = rr;
                }
            }
        }
        if (cnt == 0)
        {
            cout << 0 << ' ' << m << endl;
            continue;
        }
        sort(dak + 1, dak + cnt + 1);
        for (int i = 1; i <= cnt; ++i)
        {
            ex[i] = false;
        }
        int mn = m + 1;
        for (int i = cnt; i >= 1; --i)
        {
            if (mn <= dak[i].r)
            {
                ex[i] = true;
            }
            else
            {
                mn = dak[i].r;
            }
        }
        int ans = 0;
        int tmp = 0;
        for (int i = 1; i <= cnt; ++i)
        {
            if (ex[i])
                continue;
            if (dak[i].l > tmp)
            {
                ans++;
                tmp = dak[i].r;
            }
        }
        cout << cnt << ' ' << m - ans << endl;
    }
    return 0;
}