Untitled

mail@pastecode.io avatar
unknown
plain_text
21 days ago
1.1 kB
3
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];
deque<int> s ;
int solve() {
    for ( int i = 1; i <= n; i++ ) {
        while ( !s.empty() && c[i].first - c[s.front()].first > d ) s.pop_front() ;
        while ( !s.empty() && c[i].second > c[s.front()].second ) s.pop_back() ;
        if ( !s.empty() ) L[i] = 1;
        s.push_back(i) ;
    }
    s.clear() ;
    for ( int i = n; i >= 1; i-- ) {
        while ( !s.empty() && c[s.front()].first - c[i].first > d ) s.pop_front() ;
        while ( !s.empty() && c[i].second > c[s.front()].second ) s.pop_back() ;
        if ( !s.empty() ) R[i] = 1;
        s.push_back(i) ;
    }
    int dem = 0 ;
    for ( int i = 1; i<=n; i++ )
        if ( L[i] + R[i] == 2 ) dem++ ;
    return dem ;
}

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) ;
    cout << solve() ;
}
Leave a Comment