| 123456 |
- #include <algorithm>
- #include <iostream>
- #include <utility>
- #include <vector>
- using namespace std;
- int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin>>T;while(T--){int n,m;long long L,V;cin>>n>>m>>L>>V;struct Car{long long d,v,a;};vector<Car>cars(n);for(auto&x:cars)cin>>x.d>>x.v>>x.a;vector<long long>p(m);for(auto&x:p)cin>>x;vector<pair<int,int>>intervals;long long limit=V*V;for(auto car:cars){int first=lower_bound(p.begin(),p.end(),car.d)-p.begin();if(first==m)continue;auto fast=[&](int idx){return car.v*car.v+2*car.a*(p[idx]-car.d)>limit;};int l=-1,r=-1;if(car.a>=0){if(car.a==0){if(car.v>V)l=first,r=m-1;}else{int lo=first,hi=m-1;while(lo<hi){int mid=(lo+hi)/2;if(fast(mid))hi=mid;else lo=mid+1;}if(fast(lo))l=lo,r=m-1;}}else if(car.v>V){int lo=first,hi=m-1;while(lo<hi){int mid=(lo+hi+1)/2;if(fast(mid))lo=mid;else hi=mid-1;}if(fast(lo))l=first,r=lo;}if(l!=-1)intervals.push_back({r,l});}sort(intervals.begin(),intervals.end());int kept=0,last=-1;for(auto[r,l]:intervals)if(last<l)last=r,++kept;cout<<intervals.size()<<' '<<m-kept<<'\n';}}
|
