Submission #1060642

#TimeUsernameProblemLanguageResultExecution timeMemory
1060642oviyan_gandhiLightning Rod (NOI18_lightningrod)C++17
100 / 100
254 ms156408 KiB
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")

#include <bits/stdc++.h>

using namespace std;

inline int readInt() {
  int x = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9')
    ch = getchar_unlocked();
  while (ch >= '0' && ch <= '9') {
    x = (x << 3) + (x << 1) + ch - '0';
    ch = getchar_unlocked();
  }
  return x;
}

struct Point {
  int x, y;
  Point() {}

  bool protects(const Point &p) { return abs(x - p.x) <= y - p.y; }
  bool is_protected_by(const Point &p) { return abs(p.x - x) <= p.y - y; }
};

int main() {
  int N = readInt();
  vector<Point> a(N);
  for (int i = 0; i < N; i++) {
    a[i].x = readInt();
    a[i].y = readInt();
  }

  stack<Point> stk;
  for (int i = 0; i < N; ++i) {
    if (stk.empty()) {
      stk.push(a[i]);
      continue;
    }
    if (a[i].is_protected_by(stk.top())) {
      continue;
    }
    while (!stk.empty() && a[i].protects(stk.top())) {
      stk.pop();
    }
    stk.push(a[i]);
  }
  cout << stk.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...