90分Wa on #6求调
查看原帖
90分Wa on #6求调
1283408
nyssc楼主2024/11/13 20:16
#include <bits/stdc++.h>
using namespace std;
struct Car{
    int d,v,a;
};
struct Interval{
    int l, r;
};
struct CaughtInterval{
    int l, r, last_cam;
};
int main(){
    //freopen("test.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n, m, V, L;
        cin >> n >> m >> L >> V;
        vector<Car> cars(n);
        vector<int> cams(n);
        for(int i = 0;i<n;i++){
            cin >> cars[i].d >> cars[i].v >> cars[i].a;
        }
        for(int i = 0;i<m;i++){
            cin >> cams[i];
        }
        vector<Interval> intervals;
        intervals.reserve(n);
        for(int i = 0;i<n;i++){
            const Car& car = cars[i];
            if(car.a > 0){
                if(car.v > V){
                    intervals.push_back(Interval{car.d, L});
                }else{
                    int dividend = V * V - car.v * car.v;
                    int divisor = 2 * car.a;
                    int start_dist = dividend / divisor;
                    if(dividend % divisor == 0){
                        start_dist++;
                    }
                    if(start_dist <=L){
                        intervals.push_back(Interval{car.d + start_dist, L});
                    }
                }
            }else if(car.a < 0){
                if(car.v > V){
                    int dividend = car.v * car.v - V * V;
                    int divisor = -2 * car.a;
                    int end_dist = dividend / divisor;
                    if(dividend % divisor == 0){
                        end_dist--;
                    }
                    intervals.push_back(Interval{car.d, min(car.d + end_dist, L)});
                }
            }else{
                if(car.v > V){
                    intervals.push_back(Interval{car.d, L});
                }
            }
        }
        vector<CaughtInterval> caught;
        caught.reserve(intervals.size());
        for(int i{};i<intervals.size();i++){
            const Interval& iv = intervals[i];
            int l{ -1 }, r{m - 1};
            while(l < r){
                int mid = (l + r + 1) >> 1;
                if(cams[mid] <= iv.r){
                    l = mid;
                }else{
                    r = mid - 1;
                }
            }
            if(l != -1 && cams[l] >= iv.l){
                caught.push_back(CaughtInterval{iv.l, iv.r, cams[r]});
            }
        }
        cout << caught.size() << " ";
        sort(caught.begin(), caught.end(), [](const CaughtInterval& a, const CaughtInterval& b){
            return a.r < b.r;
        });
        int used_cams{};
        for(int i{};i<caught.size();){
            int cur_cam = caught[i].last_cam;
            used_cams++;
            int j = i + 1;
            while(j < caught.size() && cur_cam >= caught[j].l && cur_cam <= caught[j].r){
                j++;
            }
            i=j;
        }
        cout << m - used_cams << '\n';
    }
}
2024/11/13 20:16
加载中...