求条
查看原帖
求条
1014179
Dream_in_Wind楼主2024/11/9 14:15
#include <bits/stdc++.h>
using namespace std;
inline int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
int n, m, L, k, d[100005], v[100005], a[100005], p[100005], cnt;
struct M
{
    int l, r;
    bool operator<(const M tmp) const
    {
        return (r ^ tmp.r) ? r < tmp.r : l < tmp.l;
    }
} q[100005];
inline bool check(int l, int r)
{
    int x = upper_bound(p + 1, p + m + 1, r) - p - 1;
    return (p[x] >= l && p[x] <= r);
}
int main()
{
    // freopen("detect.in", "r", stdin);
    // freopen("detect.out", "w", stdout);
    int T = read();
    while (T--)
    {
        cnt = 0;
        n = read(), m = read(), L = read(), k = read();
        for (int i = 1; i <= n; i++)
        {
            d[i] = read(), v[i] = read(), a[i] = read();
        }
        for (int i = 1; i <= m; i++)
        {
            p[i] = read();
        }
        sort(p + 1, p + m + 1);
        for (int i = 1; i <= n; i++)
        {
            if (a[i] < 0)
            {
                if (v[i] <= k)
                    continue;
                int l = d[i], r;
                double dx = (k * k - v[i] * v[i]) / 2.0 / (double)a[i];
                double x = d[i] + dx;
                if (ceil(x) == x)
                    r = ceil(x) + 1;
                else
                    r = ceil(x);
                if (r > L)
                    r = L;
                if (check(l, r))
                    q[++cnt] = {l, r};
            }
            else if (a[i] == 0)
            {
                if (v[i] > k)
                {
                    if (check(d[i], L))
                        q[++cnt] = {d[i], L};
                }
            }
            else
            {
                int l, r = L;
                if (v[i] > k)
                {
                    l = d[i];
                }
                else
                {
                    double dx = (k * k - v[i] * v[i]) / 2.0 / (double)a[i];
                    double x = d[i] + dx;
                    if (ceil(x) == x)
                        l = (int)(ceil(x) + 1);
                    else
                        l = (int)ceil(x);
                }
                if (l > r)
                    continue;
                if (check(l, r))
                    q[++cnt] = {l, r};
            }
        }
        sort(q + 1, q + cnt + 1);
        int ans = 0, lst = -1;
        for (int i = 1; i <= cnt; i++)
        {
            if (q[i].l > lst)
            {
                ans++;
                lst = p[upper_bound(p + 1, p + m + 1, q[i].r) - p - 1];
            }
        }
        printf("%lld %lld\n", cnt, m - ans);
    }
    return 0;
}
	
2024/11/9 14:15
加载中...