oj.uz

Submission #1023160

# Submission time Handle Problem Language Result Execution time Memory
1023160 2024-07-14T11:24:09 Z avighna Lightning Rod (NOI18_lightningrod) C++17
100 / 100
 369 ms 262144 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 338 ms 262144 KB Output is correct
2 Correct 332 ms 262144 KB Output is correct
3 Correct 300 ms 260512 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 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 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 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 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 604 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 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 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 604 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 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 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 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 604 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 8 ms 5408 KB Output is correct
15 Correct 8 ms 5212 KB Output is correct
16 Correct 9 ms 5208 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 225636 KB Output is correct
2 Correct 305 ms 225508 KB Output is correct
3 Correct 290 ms 220052 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 338 ms 262144 KB Output is correct
2 Correct 332 ms 262144 KB Output is correct
3 Correct 300 ms 260512 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 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 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 0 ms 348 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 8 ms 5408 KB Output is correct
18 Correct 8 ms 5212 KB Output is correct
19 Correct 9 ms 5208 KB Output is correct
20 Correct 345 ms 225636 KB Output is correct
21 Correct 305 ms 225508 KB Output is correct
22 Correct 290 ms 220052 KB Output is correct
23 Correct 369 ms 246824 KB Output is correct
24 Correct 332 ms 227832 KB Output is correct
25 Correct 348 ms 211928 KB Output is correct