90pts WA on#1 求条,玄关
查看原帖
90pts WA on#1 求条,玄关
945845
Chernobog_Belobog楼主2024/11/2 21:34
#include <bits/stdc++.h>
using namespace std;

int t , n , m , len , v , p[100009] , pre , tmp , ans1 , ans2;
struct node {
    int d , v , a , l , r;
    bool operator < (const node &b) const {
        return l < b.l;
    }
}c[100009];
bool f[100009];

void work() {
    memset(f , 0 , sizeof f);
    cin >> n >> m >> len >> v; pre = len + 1 , ans1 = ans2 = 0;
    for (int i = 1 ; i <= n ; i++) cin >> c[i].d >> c[i].v >> c[i].a;
    for (int i = 1 ; i <= m ; i++) cin >> p[i];
    for (int i = 1 ; i <= n ; i++) {
        if (c[i].v > v && c[i].a < 0) {
            c[i].l = c[i].d;
            c[i].r = min(len , (int)ceil(1.0 * (v * v - c[i].v * c[i].v) / (2 * c[i].a)) - 1 + c[i].d);
        } else if (c[i].v > v) {
            c[i].l = c[i].d;
            c[i].r = len;
        } if (c[i].v == v && c[i].a > 0) {
            c[i].l = c[i].d + 1;
            c[i].r = len;
        } else if (c[i].v == v) {
            c[i].l = len + 1;
            c[i].r = len;
        } if (c[i].v < v && c[i].a > 0) {
            c[i].l = max(c[i].d , (int)floor(1.0 * (v * v - c[i].v * c[i].v) / (2 * c[i].a)) + 1 + c[i].d);
            c[i].r = len;
        } else if (c[i].v < v) {
            c[i].l = len + 1;
            c[i].r = len;
        }
        //cout << c[i].l << " " << c[i].r << endl;
        tmp = lower_bound(p + 1 , p + m + 1 , c[i].l) - p;
        if (p[tmp] >= c[i].l && p[tmp] <= c[i].r) ans1++;
    }
    sort(c + 1 , c + n + 1);
    for (int i = n ; i >= 1 ; i--) {
        tmp = lower_bound(p + 1 , p + m + 1 , c[i].l) - p;
        if (p[tmp] < c[i].l || p[tmp] > c[i].r) f[i] = 1;
        else if (c[i].l > len) f[i] = 1;
        else if (c[i].r >= pre) f[i] = 1;
        else pre = c[i].r;
    } pre = 0;
    //for (int i = 1 ; i <= n ; i++) cout << f[i] << " "; cout << endl;
    for (int i = 1 ; i <= n ; i++) {
        if (f[i]) continue;
        if (p[pre] >= c[i].l && p[pre] <= c[i].r) continue;
        pre = upper_bound(p + 1 , p + m + 1 , c[i].r) - p - 1;
        ans2++;
    }
    cout << ans1 << " " << m - ans2 << endl;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> t;
    while (t--) work();
    return 0;
}
2024/11/2 21:34
加载中...