90pts WA#9 求条
查看原帖
90pts WA#9 求条
612722
JustPureH2O楼主2024/10/29 20:27
#include <bits/stdc++.h>
#define N 100010
#define M 1000010
using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

int d[N], v[N], a[N];
int pos[M];
PII rec[N];

bool cmp(const PII &l, const PII &r) {
    return l.second < r.second;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

#ifndef ONLINE_JUDGE
    freopen("detect4.in", "r", stdin);
    freopen("detect4.out", "w", stdout);
#endif
    double st = clock();
    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 >> pos[i];
        sort(pos + 1, pos + 1 + m);
        int ans1 = 0, ans2 = 0;
        for (int i = 1; i <= n; i++) {
            int idx = lower_bound(pos + 1, pos + 1 + m, d[i]) - pos - 1;
            rec[i] = {0, m + 100};
            if (d[i] > pos[m]) continue;
            if (!a[i]) {
                if (v[i] > V) {
                    ans1++;
                    rec[i] = {idx + (d[i] > pos[idx]), m};
                }
            } else if (a[i] > 0) {
                if ((ll) v[i] * v[i] + 2 * a[i] * (pos[m] - d[i]) > (ll) V * V) {
                    int idx1 = lower_bound(pos + 1, pos + 1 + m, d[i] * 1.0 + (v[i] * v[i] * 1.0 - V * V * 1.0) / (2.0 * a[i])) - pos - 1;
                    ans1++;
                    rec[i] = {idx1 + (d[i] > pos[idx1]), m};
                }
            } else {
                if ((ll) v[i] * v[i] + 2 * a[i] * (pos[idx + 1] - d[i]) > (ll) V * V) {
                    double dis = d[i] * 1.0 + (V * V * 1.0 - v[i] * v[i] * 1.0) / (2.0 * a[i]);
                    int idx1 = lower_bound(pos + 1, pos + 1 + m, dis) - pos - 1;
                    ans1++;
                    rec[i] = {idx + (d[i] > pos[idx]), idx1};
                }
            }
        }
        sort(rec + 1, rec + 1 + n, cmp);
        int R = 0;
        for (int i = 1; i <= ans1; i++) {
            if (rec[i].first <= R && R <= rec[i].second) continue;
            R = rec[i].second;
            ans2++;
        }
        cout << ans1 << ' ' << m - ans2 << '\n';
    }
    cerr << (clock() - st) / CLOCKS_PER_SEC << "s" << endl;
    return 0;
}

记录

2024/10/29 20:27
加载中...