oj.uz

Submission #1060642

# Submission time Handle Problem Language Result Execution time Memory
1060642 2024-08-15T20:12:05 Z oviyan_gandhi Lightning Rod (NOI18_lightningrod) C++17
100 / 100
 254 ms 156408 KB 
#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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 156408 KB Output is correct
2 Correct 235 ms 155900 KB Output is correct
3 Correct 203 ms 151028 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 6 ms 1820 KB Output is correct
15 Correct 7 ms 1884 KB Output is correct
16 Correct 7 ms 2392 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 129332 KB Output is correct
2 Correct 254 ms 129108 KB Output is correct
3 Correct 222 ms 126040 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 156408 KB Output is correct
2 Correct 235 ms 155900 KB Output is correct
3 Correct 203 ms 151028 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 6 ms 1820 KB Output is correct
18 Correct 7 ms 1884 KB Output is correct
19 Correct 7 ms 2392 KB Output is correct
20 Correct 230 ms 129332 KB Output is correct
21 Correct 254 ms 129108 KB Output is correct
22 Correct 222 ms 126040 KB Output is correct
23 Correct 246 ms 71196 KB Output is correct
24 Correct 228 ms 71252 KB Output is correct
25 Correct 239 ms 74700 KB Output is correct