求调
查看原帖
求调
905071
wbs123456楼主2024/11/3 14:10
#include <bits/stdc++.h>
#define int long long

using namespace std;
const signed MAXN = 1e5 + 5;
struct line {
    int l, r;
};
bool cmp(line x, line y) { return x.r < y.r; }
line car[MAXN], bad_car[MAXN];
int ans1, ans2, t, n, m, L, V, d[MAXN], v[MAXN], a[MAXN], p[MAXN], cs[MAXN], sum[MAXN];
bool P[MAXN];
signed main() {
    cin >> t;
    while (t--) {
        memset(d, 0, sizeof d);
        memset(v, 0, sizeof v);
        memset(a, 0, sizeof a);
        memset(p, 0, sizeof p);
        ans1 = ans2 = 0;
        cin >> n >> m >> L >> V;
        for (int i = 1; i <= n; i++) {
            cin >> d[i] >> v[i] >> a[i];
            if (v[i] > V) {
                if (a[i] >= 0) {
                    car[i].l = d[i];
                    car[i].r = L;
                    // int l=lower_bound()
                    // if(car[i].l<)
                } else {
                    car[i].l = d[i];
                    int tmp1 = abs(V * V - v[i] * v[i]);
                    int tmp2 = abs(2 * a[i]);
                    if (tmp1 % tmp2 == 0)
                        car[i].r = d[i] + tmp1 / tmp2;
                    else
                        car[i].r = d[i] + tmp1 / tmp2;
                }
            } else if (v[i] == V) {
                if (a[i] <= 0) {
                    car[i].l = -1;
                    car[i].r = -1;
                } else if (a[i] > 0) {
                    car[i].l = d[i] + 1;
                    car[i].r = L;
                }
            } else if (v[i] < V) {
                if (a[i] <= 0) {
                    car[i].l = -1;
                    car[i].r = -1;
                } else if (a[i] > 0) {
                    car[i].r = L;
                    int tmp1 = abs(V * V - v[i] * v[i]);
                    int tmp2 = abs(2 * a[i]);
                    car[i].l = d[i] + tmp1 / tmp2;
                    if (car[i].l > car[i].r) {
                        car[i].l = -1;
                        car[i].r = -1;
                    }
                }
            }
        }
        for (int i = 1; i <= m; i++) {
            cin >> p[i];
        }
        for (int i = 1; i <= n; i++) {
            if (car[i].l == -1) {
                continue;
            }
            int it = lower_bound(p + 1, p + 1 + m, car[i].l) - p;
            if (p[it] <= car[i].r && it != 1 + m) {
                ans1++;
            }
                bad_car[ans1].l = car[i].l;
                bad_car[ans1].r = car[i].r;
            } else {
                car[i].l = -1;
                car[i].r = -1;
            }
        }
        sort(bad_car + 1, bad_car + 1 + n, cmp);
        int j = 0;
        for (int i = 1; i <= ans1; i++) {
            if (bad_car[i].l > j) {
                ans2++;
                j = bad_car[i].r;
            }
        }
        cout << ans1 << " " << m - ans2 << endl;
    }
    return 0;
}
2024/11/3 14:10
加载中...