80tps WA on #8 # 10求调

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define f(i, from, to, ...) for (int i = from, ##__VA_ARGS__; i <= to; ++i)
#define w(i, start, flag, step, ...) for (int i = start, ##__VA_ARGS__; flag; step)
#define fi(i, s, t, ...) for (int i = s; i <= t && input(__VA_ARGS__); ++i)
#define fdi(i, s, t, ...) for (int i = s, ##__VA_ARGS__; i <= t && input(__VA_ARGS__); ++i)
#define di(...)      \
    int __VA_ARGS__; \
    input(__VA_ARGS__)
#define double long double
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;
template <class T>
using pqr = priority_queue<T, vector<T>, greater<T>>;
template <class T>
using pq = priority_queue<T>;

template <typename... Args>
bool input(Args &...args)
{
    return static_cast<bool>((... && (cin >> args)));
}

template <class T, typename... Args>
void print(const T &prefix, Args... args)
{
    cout << prefix << " ", (..., (cout << args << " ")), cout << endl;
}
constexpr int inf = LLONG_MAX;
constexpr double eps = 1e-9;
int n, m, l, v;
struct Range
{
    int l, r;
    bool operator<(const Range &x) const
    {
        return r > x.r;
    }
};
double calc_v(double x, double a, double v0)
{
    return sqrt(v0 * v0 + 2 * a * x);
}
double calc_x(double v0, double a, double t)
{
    return v0 * t + 0.5 * a * t * t;
}
void solve()
{
    input(n, m, l, v);
    vector<int> p;
    vector<tuple<int, int, int>> cars;
    pq<Range> q;
    int cnt1 = 0, cnt2 = 0;
    fdi(i, 1, n, d, v0, a) cars.emplace_back(d, v0, a);
    fdi(i, 1, m, tmp) p.emplace_back(tmp);

    for (auto [d, v0, a] : cars)
    {
        if (d > p.back())
            continue;
        if (a > 0)
        {
            int last_p = p.back();
            double last_v = calc_v(last_p - d, a, v0);
            if (last_v > v)
                cnt1++;
        }
        else
        {
            auto first_pos = lower_bound(p.begin(), p.end(), d);

            double first_v = calc_v(*first_pos - d, a, v0);
            if (first_v > v)
                cnt1++;
        }
    }

    for (auto [d, v0, a] : cars)
    {
        if (a > 0)
        {
            double over_time = (v - v0) * 1.0 / a;
            int over_start = floor(calc_x(v0, a, over_time)) + d;
            if (over_start > p.back())
                continue;
            q.push({over_start, l});
        }
        else if (a == 0)
        {
            if (v0 > v)
                q.push({d, l});
        }
        else
        {
            if (v0 <= v)
                continue;
            double last_time = (v - v0) * 1.0 / a;
            int last_over = floor(calc_x(v0, a, last_time)) + d;
            q.push({d, min(l,last_over)});
        }
    }
    int now_pos = -1;
    while (q.size())
    {
        auto [l, r] = q.top();
        q.pop();
        auto last_it = lower_bound(p.begin(), p.end(), r);
        int last_pos;
        if (*last_it != 0 && *last_it != r)
            last_pos = *(last_it - 1);
        else if (*last_it == r)
            last_pos = *last_it;
        else
            last_pos = p.back();
        if (last_pos < l || last_pos > r)
        {
            continue;
        }
        else if (now_pos >= l && now_pos <= r)
        {
            continue;
        }
        else
            now_pos = last_pos, cnt2++;
    }
    print(cnt1, m - cnt2);
}
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    di(T);
    while (T--)
        solve();
    return 0;
}