rt,考场代码,过了所有大样例,求助。
#include<bits/stdc++.h>
using namespace std;
long long T;
long long n,m;//车辆 测速仪数量
double l,V;//主干道长度、主干道限速
double d[100005],v[100005],a[100005];//车驶入位置,初始速度、加速度
double dis[100005];//测速仪位置
struct node {
int le,ri;//左右端点
friend bool operator <(node x,node y) {
return x.ri < y.ri;
}
}ed[100005];
int main() {
scanf("%lld",&T);
while(T--) {
long long ans1 = 0;
scanf("%lld %lld %lf %lf",&n,&m,&l,&V);
for(int i = 1;i <= n;i++) scanf("%lf %lf %lf",&d[i],&v[i],&a[i]);
for(int i = 1;i <= m;i++) scanf("%lf",&dis[i]);
//超速车辆
for(int i = 1;i <= n;i++) {
if(a[i] > 0) {
if(dis[m] >= d[i]) {
if(v[i] * v[i] + 2.0 * a[i] * (dis[m] - d[i]) > V * V) {
ans1++;
int l = 1,r = m,mid;
while(l < r) {
mid = (l + r) >> 1;
if(dis[mid] >= d[i] and v[i] * v[i] + 2.0 * a[i] * (dis[m] - d[i]) > V * V) r = mid;
else l = mid + 1;
}
ed[ans1].le = l,ed[ans1].ri = m;
}
}
}
else if(a[i] == 0) {
if(dis[m] >= d[i] and v[i] > V) {
ans1++;
int l = 1,r = m,mid;
while(l < r) {
mid = (l + r) >> 1;
if(dis[mid] >= d[i]) r = mid;
else l = mid + 1;
}
ed[ans1].le = l,ed[ans1].ri = m;
}
}
else {
int l = 1,r = m,mid;
while(l < r) {
mid = (l + r) >> 1;
if(dis[mid] >= d[i]) r = mid;
else l = mid + 1;
}
if(v[i] * v[i] + 2.0 * a[i] * (dis[l] - d[i]) > V * V) {
ans1++,ed[ans1].le = l,r = m;
while(l < r) {
mid = (l + r + 1) >> 1;
if(dis[mid] >= d[i] and v[i] * v[i] + 2.0 * a[i] * (dis[mid] - d[i]) > V * V) l = mid;
else r = mid - 1;
}
ed[ans1].ri = l;
}
}
//printf("%lld %lld\n",i,ans1);
}
//
sort(ed + 1,ed + ans1 + 1);
long long ans2 = 0;
//for(int i = 1;i <= ans1;i++)printf("__________%lld %lld\n",ed[i].le,ed[i].ri);
for(int i = 1,j = 0;i <= ans1;i++) {
if(ed[i].le > ed[j].ri) {
ans2++,j = i;
}
}
printf("%lld %lld\n",ans1,m - ans2);
}
return 0;
}