Target Practice II

Suite_No1_G · 2024-02-27 07:49:06 · 题解

省流：比赛时题没看懂爆零，后来看懂题后一遍过。

分开考虑上界和下界，则答案为最小上界减去最大下界。

分析了一下，发现矩形右下角的点只能由斜率是正数的牛射掉（从下往上射箭），矩形右上角的点只能由斜率是负数的牛射掉（从上往下射箭），因为题目说了不允许箭穿过矩形内部。

对于矩形左上角和左下角，发现都在一条直线上，那么这条直线上面部分的点就从下往上射掉（即斜率为正），直线下面的点就从上往下射掉（即斜率为负）。

然后，根据这个性质，如果斜率为正的牛数量小于 n 或者斜率为负的牛数量小于 n，则无解。

以下界为例（上界处理方法同理，只不过注意符号），我们发现答案具有单调性，所以可以二分出最大上界。假设当前二分到 mid。

检验的时候贪心处理：对于每一个点（矩形右下角），设其坐标为 (x,y)，则找到斜率的 绝对值 最大的一头牛，用这头牛射掉这个点，设斜率为 s，我们发现 y-x×s≥mid。找到 绝对值 最大的牛，并用这头牛射掉，并删除这头牛。

这个贪心方法是正确的，因为如果一个点能用斜率为 s1 和 s2 的点射掉，且 s1≥s2，（此情况为下界），那么用斜率为 s1 的牛来射这个点不会劣。

这样，我们 O(n) 枚举点，O(n) 枚举斜率，再加上二分的复杂度，时间复杂度为 O(n^2 \log V)，可以过前面 9 个点。

考虑优化。我们发现瓶颈在于 O(n) 枚举斜率，我们可以使用 multiset 来记录斜率，然后查找删除，时间复杂度优化到 O(\log n)。

综上，可以优化到 O(n \log n \log V)。注意上下界的区别。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+10;
struct node{
    int x,y;
};
node rightDown[maxn],rightUp[maxn],Line[maxn];
int init[maxn];
multiset<int> slope_pos, slope_nega;
int n,X;
int tot1=0,tot2=0,tot3=0;
int len1=0,len2=0;
int P[maxn],N[maxn];

bool cmp(node i,node j){
    return i.y>j.y;
}

bool check1(int mid){
    slope_pos.clear();
    for (int i=1;i<=len1;i++) slope_pos.insert(P[i]);
    int left=len1;
    for (int i=1;i<=tot1;i++){
        int need=(rightDown[i].y-mid)/rightDown[i].x;
        multiset<int>::iterator it=slope_pos.upper_bound(need);
        if (it==slope_pos.begin()) return false;
        it--;
        int num=(*it);
        slope_pos.erase(slope_pos.find(num));
        left--;
    }

    for (int i=1;i<=left;i++){
        int need=(Line[i].y-mid)/X;
        multiset<int>::iterator it=slope_pos.upper_bound(need);
        if (it==slope_pos.begin()) return false;
        it--;
        int num=(*it);
        slope_pos.erase(slope_pos.find(num));
    }
    return true;
}

bool check2(int mid){
    slope_nega.clear();
    for (int i=1;i<=len2;i++) slope_nega.insert(N[i]);
    int left=len2;
    for (int i=1;i<=tot2;i++){
        int need=(mid-rightUp[i].y)/rightUp[i].x;
        multiset<int>::iterator it=slope_nega.upper_bound(need);
        if (it==slope_nega.begin()) return false;
        it--;
        int num=(*it);
        slope_nega.erase(slope_nega.find(num));
        left--;
    }

    for (int i=tot3-left+1;i<=tot3;i++){
        int need=(mid-Line[i].y)/X;
        multiset<int>::iterator it=slope_nega.upper_bound(need);
        if (it==slope_nega.begin()) return false;
        it--;
        int num=(*it);
        slope_nega.erase(slope_nega.find(num));
    }
    return true;
} 

void solve(){
    slope_pos.clear(); slope_nega.clear();
    scanf("%lld%lld",&n,&X);
    tot1=0,tot2=0,tot3=0;
    len1=0,len2=0;
    for (int i=1;i<=n;i++){
        int y_1,y_2,x_2;
        scanf("%lld%lld%lld",&y_1,&y_2,&x_2);
        rightDown[++tot1]=(node){x_2,y_1};
        rightUp[++tot2]=(node){x_2,y_2};
        Line[++tot3]=(node){X,y_1}, Line[++tot3]=(node){X,y_2};
    }
    sort(Line+1,Line+tot3+1,cmp);

    for (int i=1;i<=4*n;i++){
        int num; scanf("%lld",&num);
        if (num>0) P[++len1]=num;
        else N[++len2]=-num;    
    }

    if (len1<n||len2<n){
        printf("-1\n");
        return;
    }

    int l=-2e18,r=2e18;
    int best1=-2e18,best2=2e18;
    while (l<=r){
        int mid=(l+r)/2;
        if (check1(mid)){
            best1=mid;
            l=mid+1;
        }else r=mid-1;
    }

    if (best1==-2e18){
        printf("-1\n"); return;
    }

    l=best1,r=2e18;
    while (l<=r){
        int mid=(l+r)/2;
        if (check2(mid)){
            best2=mid;
            r=mid-1;
        }else l=mid+1;
    }
    if (best2==2e18){
        printf("-1\n"); return;
    }   
    printf("%lld\n",best2-best1);
}

signed main(){
//  freopen("random.in","r",stdin);
//  freopen("wrong.out","w",stdout);
    int T;
    scanf("%lld",&T);
    while (T--){
        solve();
    }
    return 0;
}