[HOJ] 66 - Farmer John

#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;
struct P{
    int a,b;
    friend bool operator < (P a,P b){
        return a.a>b.a;
    }
};
struct T{
    int a,b;
    friend bool operator < (T a,T b){
        return a.a<b.a;
    }
};
int a[5000005],b[5000005];
priority_queue<T> L;
priority_queue<P> R;
int main(){
    int n,m,x,y,A,B,i,j;
    long long int ans=0;
    scanf("%d%d%d%d",&n,&m,&x,&y);
    for(i=0;i<m;i++){
        scanf("%d%d",&a[i],&b[i]);
        L.push((T){a[i],i});
        R.push((P){a[i]+b[i],i});
        if(i>=y-1){
            while(L.top().b<=i-y) L.pop();
            while(R.top().b<=i-y) R.pop();
            A=L.top().a;
            B=R.top().a;
            if(B-A>=x) ans+=B-A-x+1;
        }
    }
    while(L.size()) L.pop();
    while(R.size()) R.pop();
    for(i=0;i<m;i++){
        L.push((T){a[i],i});
        R.push((P){a[i]+b[i],i});
        if(i>=x-1){
            while(L.top().b<=i-x) L.pop();
            while(R.top().b<=i-x) R.pop();
            A=L.top().a;
            B=R.top().a;
            if(B-A>=y) ans+=B-A-y+1;
        }
    }
    if(x==y) ans/=2;
    printf("%lld\n",ans);
}