90 分哪里挂了啊/kel
查看原帖
90 分哪里挂了啊/kel
974277
水星湖psgqwq楼主2024/10/26 22:17
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define l first
#define r second
const int N = 5e5 + 5;
int a[N], v[N], d[N], p[N], b[N], cur;
pair<int, int> c[N];
void solve() {
    cur = 0;
    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];
    for(int i = 1; i <= n; i++) {
        if(a[i] <= 0) {
            int j = lower_bound(p + 1, p + 1 + m, d[i]) - p;
            if(j <= m && v[i] * v[i] + 2 * a[i] * (p[j] - d[i]) > V * V)
                b[++cur] = i;
        }
        else if(d[i] <= p[m] && v[i] * v[i] + 2 * a[i] * (p[m] - d[i]) > V * V)
            b[++cur] = i;
    }
    cout << cur << ' ';
    if(!cur) return cout << m << "\n", void();
    for(int i = 1; i <= cur; i++) {
        if(a[b[i]] < 0) {
            c[i].l = d[b[i]];
            c[i].r = d[b[i]] + (V * V - v[b[i]] * v[b[i]]) / (2 * a[b[i]]) - ((V * V - v[b[i]] * v[b[i]]) % (2 * a[b[i]]) == 0);
        }
        if(a[b[i]] > 0) {
            c[i].r = l;
            c[i].l = d[b[i]] + (V * V - v[b[i]] * v[b[i]]) / (2 * a[b[i]]) + ((V * V - v[b[i]] * v[b[i]]) % (2 * a[b[i]]) == 0);
        }
        if(a[b[i]] == 0) 
            c[i] = {d[b[i]], l};
    }
    sort(c + 1, c + cur + 1, [&](pair<int, int> a, pair<int, int> b){return a.second < b.second;}); 
    int ans = 0, j = 1, lst = -1;
    for(int i = 1; i <= cur; i++) {
        if(c[i].l <= lst) continue;
        while(j <= m && c[i].r >= p[j]) j++;
        ans++;
        lst = p[j - 1];
    }
    cout << m - ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("detect10.in", "r", stdin);
    //freopen("detect10.out", "w", stdout);
    int T; cin >> T;
    while(T--) solve();

    return 0;
}
2024/10/26 22:17
加载中...