Submission #873532

#	Time	Username	Problem	Language	Result	Execution time	Memory
873532		dsyz	Lightning Rod (NOI18_lightningrod)	C++17	100 / 100	753 ms	262144 KiB

Main

#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';    
}

• Subtask 1: 4 / 4
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 26 / 26
• Subtask 6: 10 / 10
• Subtask 7: 20 / 20