989D. A Shade of Moonlight[单调栈]

Gathering darkness shrouds the woods and the world. The moon sheds its light on the boat and the river.”To curtain off the moonlight should be hardly possible; the shades present its mellow beauty and restful nature.” Intonates Mino.

“See? The clouds are coming.” Kanno gazes into the distance.

“That can’t be better,” Mino turns to Kanno.

The sky can be seen as a one-dimensional axis. The moon is at the origin whose coordinate is $0$ .

There are $n$ clouds floating in the sky. Each cloud has the same length $l$ . The $i$ -th initially covers the range of $(x_i, x_i + l)$ (endpoints excluded). Initially, it moves at a velocity of $v_i$ , which equals either $1$ or $-1$ .

Furthermore, no pair of clouds intersect initially, that is, for all $1 \leq i \lt j \leq n$ , $\lvert x_i - x_j \rvert \geq l$ .

With a wind velocity of $w$ , the velocity of the $i$ -th cloud becomes $v_i + w$ . That is, its coordinate increases by $v_i + w$ during each unit of time. Note that the wind can be strong and clouds can change their direction.

You are to help Mino count the number of pairs $(i, j)$ ( $i < j$ ), such that with a proper choice of wind velocity $w$ not exceeding $w_\mathrm{max}$ in absolute value (possibly negative and/or fractional), the $i$ -th and $j$ -th clouds both cover the moon at the same future moment. This $w$ doesn’t need to be the same across different pairs.

Input

The first line contains three space-separated integers $n$ , $l$ , and $w_\mathrm{max}$ ( $1 \leq n \leq 10^5$ , $1 \leq l, w_\mathrm{max} \leq 10^8$ ) — the number of clouds, the length of each cloud and the maximum wind speed, respectively.

The $i$ -th of the following $n$ lines contains two space-separated integers $x_i$ and $v_i$ ( $-10^8 \leq x_i \leq 10^8$ , $v_i \in {-1, 1}$ ) — the initial position and the velocity of the $i$ -th cloud, respectively.

The input guarantees that for all $1 \leq i \lt j \leq n$ , $\lvert x_i - x_j \rvert \geq l$ .

Output

Output one integer — the number of unordered pairs of clouds such that it’s possible that clouds from each pair cover the moon at the same future moment with a proper choice of wind velocity $w$ .

Examples

input 1

5 1 2
-2 1
2 1
3 -1
5 -1
7 -1

output 1

4

input 2

4 10 1
-20 1
-10 -1
0 1
10 -1

output 2

1

题目大意

给你 $n$ 朵云，每朵云的的长度为 $l$ ，风速最大为 $w$ 。

读入 $x_i$ ， $y_i$， $x_i$ 表示云的线段为 $[x_i,x_i+l]$，$y_i$ 表示云移动的速度，为1或-1。

求有多少对云，在你任意指定风速的情况下，可以在原点相遇。

题解

感谢 cogito小姐姐 。

对于云 $i$ , $j$ ，若满足 $x_i <0,x_j> 0$ 且 $y_i = 1,y_j=-1$ ，肯定可以相遇。

若满足 $x_i <0 ,x_j="">0，y_i=-1，y_j=1$ ，肯定不可以相遇。

所以要处理的只有在同一边的情况。若 $x_i=0$ 且 $y_i=-1$，我们把这种放在 $x<0$ 这一边。

然后排序后可以用单调栈之类的搞了。

判断同一边的云 $i,j$，是否可能存在焦点，如果 $y_i=y_j$，肯定不行。

若 $y_i>y_j$ 且 $x_i>x_j$ ，或者反过来，肯定不行。

当同在左边，只要判相离的时候 $y$ 小的是否在原点右边就好（是的话就有可能相交）

同在右边的时候，只要判相离的时候 $y$ 大（因为给的 $y$ 方向是向右的）的时候是否在原点左边。

时间复杂度 $O(n\log n+n)$ 。

/*
 * Author: ylx
 * LANG: c++
 * PROG: 989D
 */
#include<bits/stdc++.h>
#define ll long long
using namespace std;
void qmax(int &x,int y) {if (x<y) x=y;}
void qmin(int &x,int y) {if (x>y) x=y;}
inline int read()
{
    char s;
    int k=0,base=1;
    while ((s=getchar())!='-'&&s!=EOF&&!(isdigit(s)));
    if (s==EOF) exit(0);
    if (s=='-') base=-1,s=getchar();
    while (isdigit(s)) k=k*10+(s^'0'),s=getchar();
    return k*base;
}
inline void write(int x)
{
    static char cnt,num[15];cnt=0;
    if (!x)
    {
        putchar('0');
        return;
    }
    for (;x;x/=10) num[++cnt]=x%10;
    for (;cnt;putchar(num[cnt--]+48));
}
const ll maxn=1e5+100;
ll n,l,w,X,Y,ans,sa,sb;
int ia,ib,L,R;
struct node
{
    ll x,y;
} z[maxn],a[maxn],b[maxn];
bool cmp(node aa,node bb)
{
    return aa.x<bb.x;
}
bool check(node x,node y)
{
    if (x.x>y.x) return 0;
    ll dd=y.x-x.x+l;
    if (x.x<0) return  y.x*2+l*2-dd+dd*w>0;
    return x.x*2+dd-dd*w<0;
}
int main()
{
#ifdef ylx
    freopen("989D.in","r",stdin);
    freopen("989D.out","w",stdout);
#endif
    n=read();l=read();w=read();
    for (int i=1;i<=n;i++)
    {
        X=read();Y=read();
        if (X<0||(X==0&&Y==-1)) a[++ia].x=X,a[ia].y=Y,sa+=(Y==1);
        else b[++ib].x=X,b[ib].y=Y,sb+=(Y==-1);
    }
    ans=(ll)sa*sb;
    sort(a+1,a+ia+1,cmp);
    R=0;L=1;
    for (int i=1;i<=ia;i++) if (a[i].y==-1) z[++R]=a[i];
    for (int i=1;i<=ia;i++)
    if (a[i].y==1)
    {
        while (L<=R&&!check(a[i],z[L])) L++;
        ans+=R-L+1;
    }
    sort(b+1,b+ib+1,cmp);
    R=0;L=1;
    for (int i=ib;i>=1;i--) if (b[i].y==1) z[++R]=b[i];
    for (int i=ib;i>=1;i--)
    if (b[i].y==-1)
    {
        while (L<=R&&!check(z[L],b[i])) L++;
        ans+=R-L+1;
    }
    printf("%lld\n",ans);
    return 0;
}
//2018年 06月 12日 星期二 15:08:52 CST