Submission #873532

#TimeUsernameProblemLanguageResultExecution timeMemory
873532dsyzLightning Rod (NOI18_lightningrod)C++17
100 / 100
753 ms262144 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
int readInt() 
{
  int x = 0; 
  char ch=getchar_unlocked(); 
  bool s=1;
  while(ch<'0'||ch>'9'){if(ch=='-')s=0;ch=getchar_unlocked();}
  while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar_unlocked();}
  return s?x:-x;
}
int main() {
  ios_base::sync_with_stdio(false);cin.tie(0);
  ll N;
  N = readInt();
  pair<int,int> arr[N];
  stack<pair<int,int>> s;
  for(ll i = 0;i < N;i++){
    ll X,Y;
    X = readInt();
    Y = readInt();
    arr[i].first = X;
    arr[i].second = Y;
  }
  sort(arr,arr + N);
  for(ll i = 0;i < N;i++){
    if(s.size() == 0){
      s.push(make_pair(arr[i].first,arr[i].second));
    }else{
      if(abs(s.top().first - arr[i].first) <= (s.top().second - arr[i].second)){

      }else if(abs(arr[i].first - s.top().first) <= (arr[i].second - s.top().second)){
        while(s.size() != 0 && abs(arr[i].first - s.top().first) <= 
        (arr[i].second - s.top().second)){
          s.pop();
        }
        s.push(make_pair(arr[i].first,arr[i].second));
      }else{
        s.push(make_pair(arr[i].first,arr[i].second));
      }
    }
  }
  cout<<s.size()<<'\n';    
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...