Untitled
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