Untitled

mail@pastecode.io avatar
unknown
plain_text
24 days ago
1.1 kB
2
Indexable
Never
// y.ha
#include <bits/stdc++.h>
#define cook '\n'
#define maxn 50005
using namespace std;
int n,d,L[maxn],R[maxn];
pair<int,int> c[maxn] ;
stack<int> l,r;
void Tick() {
    l.push(0) ;
    for ( int i = 1; i <= n; i++ ) {
        while ( 2*c[i].second > c[l.top()].second ) l.pop() ;
        if ( l.top() != 0 && i - l.top() <= d ) L[i] = 1;
            else L[i] = 0;
        l.push(i) ;
    }
    r.push(0) ;
    for ( int i = n; i >= 1; i-- ) {
        while ( c[r.top()].second < 2*c[i].second ) r.pop() ;
        if ( r.top() != 0 && r.top() - i <= d ) R[i] = 1;
            else R[i] = 0;
        r.push(i) ;
    }
}

int main()
{
    ios_base::sync_with_stdio(0) ;
    cin.tie(nullptr) ;
    if(fopen("bai1.inp","r"))
        freopen("bai1.inp","r",stdin) ;
    cin >> n >> d;
    for ( int i = 1; i <= n; i++ ) cin >> c[i].first >> c[i].second ;
    sort(c+1,c+1+n) ;
    c[0].first = 0;
    c[0].second = 2e9 + 6;
    Tick() ;
    int dem = 0;
    for ( int i = 1; i <= n; i++ )
        if ( L[i] + R[i] == 2 ) dem++;
    cout << dem ;
}
Leave a Comment