P11232 [CSP-S 2024] 超速检测

Genius_Star · 2024-10-26 22:55:09 · 题解

思路：

题目已经给了提示了，位移为 s 的瞬时速度为 \sqrt{v_0^2 + 2 as}，若超速了，即：

然后将 p 从小到大排序，这样我们可以二分找到最小和最大的 [l,r] 使得在这些测速仪内会被判定为超速。

现在转化为了经典问题，给定一些区间，每个区间内必须至少选一个点，问能选的最少的点数。

两种做法，一种按左端点排序后贪心，一种转化为前缀和后差分约束即可。

时间复杂度为 O(n \log m + m \log m)。

给定一个赛后重写的 Code。

完整代码：

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
#define For(i,l,r) for(register int i=l;i<=r;i++)
#define _For(i,l,r) for(register int i=r;i>=l;i--)
using namespace std;
using namespace __gnu_pbds;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const int N = 1e5 + 10; 
inline ll read(){
    register ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(register ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
      write(x/10);
    putchar(x%10+'0');
}
struct Node{
    int l, r;
    bool operator<(const Node&rhs)const{
        if(l ^ rhs.l)
          return l < rhs.l;
        return r < rhs.r;
    }
}f[N];
int T, n, m, cnt, L, V, ans1, ans2;
int d[N], v[N], a[N], p[N];
void solve(){
    ans1 = ans2 = cnt = 0;
    n = read(), m = read(), L = read(), V = read();
    for(int i = 1; i <= n; ++i){
        d[i] = read();
        v[i] = read();
        a[i] = read();
    }
    for(int i = 1; i <= m; ++i)
      p[i] = read();
    for(int i = 1; i <= n; ++i){
        if(a[i] > 0){
            if(v[i] > V){
                int it = lower_bound(p + 1, p + m + 1, d[i]) - p;
                if(it != m + 1){
                    ++ans1;
                    f[++cnt] = {it, m};
                }
            }
            else{
                int h = d[i] + (V * V - v[i] * v[i]) / (a[i] << 1);
                int it = upper_bound(p + 1, p + m + 1, h) - p;
                if(it != m + 1){
                    ++ans1;
                    f[++cnt] = {it, m};
                }
            }
        }
        else if(a[i] < 0){
            if(v[i] <= V)
              continue;
            int h = d[i] + (v[i] * v[i] - V * V - 2 * a[i] - 1) / (-2 * a[i]);
            int it = lower_bound(p + 1, p + m + 1, d[i]) - p;
            if(it != m + 1 && p[it] < h){
                ++ans1;
                f[++cnt].l = it;
                it = lower_bound(p + 1, p + m + 1, h) - (p + 1);
                f[cnt].r = it;
            }
        }
        else{
            if(v[i] <= V)
              continue;
            int it = lower_bound(p + 1, p + m + 1, d[i]) - p;
            if(it != m + 1){
                ++ans1;
                f[++cnt] = {it, m};
            }
        }
    }
    sort(f + 1, f + cnt + 1);
    int Min = 1e5 + 10;
    for(int i = 1; i <= cnt; ++i){
//      cerr << f[i].l << ' ' << f[i].r << '\n';
        if(f[i].l > Min){
            ++ans2;
            Min = f[i].r;
            continue;
        }
        Min = min(Min, f[i].r);
    }
    if(Min != 1e5 + 10)
      ++ans2;
    write(ans1);
    putchar(' ');
    write(m - ans2);
    putchar('\n');
}
bool End;
int main(){
//  open("A.in", "A.out");
    T = read();
    while(T--)
      solve();
    cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";
    return 0;
}