80分求助
查看原帖
80分求助
217634
anonymous217楼主2024/11/4 21:30
#include <bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
const int N = 1e6 + 5;
const double eps = 1e-13;
struct node
{
    int pos, id, op;
} sped[N];
queue<int> q;
int vis[N], visck[N], pos[N], lt[N], n, m, L, V, cnt, res1, res2;
bool cmp(node a, node b) { return (a.pos == b.pos ? a.op > b.op : a.pos < b.pos); }
int FLR(int x, int y) { return x / y - !(x % y); }
int CIL(int x, int y) { return x / y + 1; }
void solve()
{
    cin >> n >> m >> L >> V;
    cnt = res1 = res2 = 0;
    for (int i = 1; i <= n; i++)
    {
        int d, v, a;
        cin >> d >> v >> a;
        vis[i] = lt[i] = 0;
        if (a == 0)
        {
            if (v <= V) continue;
            sped[++cnt] = (node){lt[i] = d, i, 1};
            sped[++cnt] = (node){L + 1, i, -1};
            continue;
        }
        int dv = (V * V - v * v), kpos;
        if (a > 0)
        {
            kpos = d + CIL(dv, 2 * a);
            if (L < kpos) continue;
            sped[++cnt] = (node){lt[i] = max(d, kpos), i, 1};
            sped[++cnt] = (node){L + 1, i, -1};
        }
        if (a < 0)
        {
            kpos = d + FLR(dv, 2 * a);
            if (kpos < d) continue;
            sped[++cnt] = (node){lt[i] = d, i, 1};
            sped[++cnt] = (node){min(L, kpos) + 1, i, -1};
        }
    }
    for (int i = 1; i <= m; i++)
        cin >> pos[i], visck[i] = 0;
    pos[0] = -1e9, pos[m + 1] = 1e9, visck[0] = 1;
    sort(sped + 1, sped + cnt + 1, cmp);
    for (int i = 1, j = 1; i <= m + 1; i++)
        for (; j <= cnt && sped[j].pos <= pos[i]; j++)
            if (sped[j].op == -1)
            {
                if (lt[sped[j].id] > pos[i - 1]) continue;
                res1++;
                if (vis[sped[j].id] || visck[i - 1]) continue;
                visck[i - 1] = 1, res2++;
                while (!q.empty() && lt[q.front()] <= pos[i - 1])
                    vis[q.front()] = 1, q.pop();
            }
            else
                q.push(sped[j].id);
    cout << res1 << " " << m - res2 << "\n";
    while (!q.empty())
        q.pop();
    return;
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    int cas;
    cin >> cas;
    while (cas--)
        solve();
    return 0;
}
2024/11/4 21:30
加载中...