답안 #1023160

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1023160	2024-07-14T11:24:09 Z	avighna	Lightning Rod (NOI18_lightningrod)	C++17	100 / 100	369 ms	262144 KB

lightningrod

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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