Submission #1023160

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023160		avighna	Lightning Rod (NOI18_lightningrod)	C++17	100 / 100	369 ms	262144 KiB

Main

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

• 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