#include<bits/stdc++.h>
using namespace std ;
const int Max = 1e5 + 10 ;
// 输入
struct Node {
double d , v , a ;
} Car[Max] ;
int p[Max] ;
int n , m ;
int T , L ;
double V ;
// 瞬时速度
double S_V( int i , double S ) {
return sqrt( ( Car[i].v * Car[i].v ) + 2 * Car[i].a * ( S - Car[i].d ) ) ;
}
// 二分
int Two_Val( int i ) {
int l = 1 , r = m ;
while( l < r ) {
int Mid = l + r >> 1 ;
if( Car[i].d <= p[Mid] ) r = Mid ;
else l = Mid + 1 ;
}
if( Car[i].d <= p[l] ) return l ;
else return -1 ;
}
int Two( int i , int Val ) {
int l = Val , r = m ;
if( l > r ) return -1 ;
int Mid ;
while( l < r ) {
if( Car[i].a >= 0 ) {
Mid = l + r >> 1 ;
if( S_V( i , p[Mid] ) <= V ) l = Mid + 1 ;
else r = Mid ;
} else {
Mid = l + r + 1 >> 1 ;
if( S_V( i , p[Mid] ) > V ) l = Mid ;
else r = Mid - 1 ;
}
}
if( S_V( i , p[l] ) > V ) return l ;
else return -1 ;
}
// 超速区间
struct Sert {
int l , r ;
bool operator < ( const Sert &A ) const {
return A.r > r ;
}
} Tr[Max] , Qr[Max] ; // Qr 优化后的
bool Rule( Sert A , Sert B ) {
if( A.l == B.l ) return A.r > B.r ;
else return A.l < B.l ;
}
priority_queue < Sert > Que ;
int Ans , Nul ;
int Rigth ;
int Cnt ; // 超速数量
void Solve( ) {
scanf("%d%d%d%lf" , &n , &m , &L , &V ) ;
for(int i = 1 ; i <= n ; i ++ ) {
scanf("%lf%lf%lf" , &Car[i].d , &Car[i].v , &Car[i].a ) ;
}
for(int i = 1 ; i <= m ; i ++ ) scanf("%d" , &p[i] ) ;
Cnt = 0 ;
for(int i = 1 , Val , Key ; i <= n ; i ++ ) {
Val = Two_Val( i ) ;
Key = Two( i , Val ) ;
if( Key != -1 ) {
if( Car[i].a >= 0 ) Tr[ ++ Cnt ] = ( Sert ) { Key , n } ;
else Tr[ ++ Cnt ] = ( Sert ) { Val , Key } ;
}
}
// 贪心
sort( Tr + 1 , Tr + Cnt + 1 , Rule ) ;
for(int i = 1 ; i <= Cnt ; i ++ ) {
while( !Que.empty( ) && Tr[i].r < Que.top( ).r ) Que.pop( ) ;
Que.push( ( Sert ) { Tr[i].l , Tr[i].r } ) ;
}
Nul = Ans = Rigth = 0 ;
while( !Que.empty( ) ) Qr[ ++ Nul ] = Que.top( ) , Que.pop( ) ;
sort( Qr + 1 , Qr + Nul + 1 , Rule ) ;
for(int i = 1 ; i <= Nul ; i ++ ) {
if( Qr[i].l > Rigth ) Ans ++ , Rigth = Qr[i].r ;
}
printf("%d %d\n" , Cnt , m - Ans ) ;
}
int main( ) {
scanf("%d" , &T ) ;
while( T -- ) Solve( ) ;
return false ;
}
很普通的思路,因为超速被检测的仪器会形成一个区间,所以可以考虑先二分求出区间,再贪心一下。
主要是大样例都过了为什么会一分没有