CodeForces 989D

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意略。

思路：

可以看成是所有的云彩照常运动，而月亮在跑。只要两个云彩相交后，在分离前月亮能赶到，就算是符合题意的。

可以知道，两个相隔越远的相向运动地云彩是越有可能符合题意的，因为它们相遇所用时间更长，这样月亮越有可能赶到。

假设云彩1为(l1,r1) ，云彩2为(l2,r2) ，r1 < l2 ，且两个云彩相向运动，云彩长度为 l 。我们令中心点p = (r1 + l2) / 2。

月亮赶到p点所需时间为runtime = p / wmax，两个云彩在相交后相离所用时间为 time = abs(r1 - l2) + l。

只要runtime < time，那么就合法。

我们现在只需要明白一个事实，在数轴上向右运动的云彩中，假设云彩1比云彩2靠左，那么云彩1对答案的贡献值中，必然还包括了云彩2对答案的贡献值。

基于以上性质，我们可以对两种方向运动的云彩分别进行排序，再用双指针。这样后面的解，就可以利用上前面计算出的值。

详见代码：

#include<bits/stdc++.h>

#define maxn 100005

using namespace std;

typedef long long LL;

double store1[maxn],store2[maxn];

int tail1,tail2,n;

double l,wmax;

int main(){

    scanf("%d%lf%lf",&n,&l,&wmax);

    double x,v;

    for(int i = ;i < n;++i){

        scanf("%lf%lf",&x,&v);

        if(v == 1.0) store1[tail1++] = x;

        else store2[tail2++] = x;

    }

    //printf("tail1 == %d tail2 == %d\n",tail1,tail2);

    sort(store1,store1 + tail1);

    sort(store2,store2 + tail2);

    LL ans = ;

    LL cur = ;

    for(int i = tail1 - ,j = tail2 - ;i >= ;--i){

        for(;j >= ;--j){

            double l1 = store1[i],r1 = l1 + l;

            double l2 = store2[j],r2 = l2 + l;

            if(l1 > l2) break;

            double midtime = fabs(r1 - l2) /  + l;

            double mid = (r1 + l2) / ;

            double time = fabs(mid) / wmax;

//            printf("time == %lf midtime == %lf\n",time,midtime);

//            printf("(1:%d,2:%d) is %s\n",i,j,time < midtime ? "OK" : "NO");

            if(time < midtime) ++cur;

            else break;

        }

        ans += cur;

    }

    printf("%lld\n",ans);

    return ;

}