답안 #522757

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
522757	2022-02-05T16:12:04 Z	nhphucqt	Lightning Rod (NOI18_lightningrod)	C++17	80 / 100	2000 ms	246288 KB

lightningrod

#include <bits/stdc++.h>

using namespace std;

struct Point {
	int x, y;
	Point() {}
	Point(int _x, int _y) {
		x = _x; y = _y;
	}
};

const int N = 1e7+7;
int numPoint, sz;
Point points[N], st[N];

bool inside(const Point &a, const Point &b) { // check if a is inside b
	return abs(b.x - a.x) <= b.y - a.y;
}

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	#ifdef NHPHUCQT
	freopen("demo.inp", "r", stdin);
	freopen("demo.out", "w", stdout);
	#endif // NHPHUCQT

	cin >> numPoint;
	for (int i = 0; i < numPoint; ++i) {
		cin >> points[i].x >> points[i].y;
	}
	for (int i = 0, cnt = 0, maxs = 0; i < numPoint; ++i) {
		cnt++; maxs = max(maxs, points[i].y);
		if (i + 1 == numPoint || points[i].x != points[i+1].x) {
			while (sz > 0 && inside(st[sz-1], Point(points[i].x, maxs))) {
				sz--;
			}
			if (sz == 0 || !inside(Point(points[i].x, maxs), st[sz-1])) {
				st[sz++] = points[i];
			}
			cnt = maxs = 0;
		}
	}
	cout << sz;
	return 0;
}

Subtask #1

4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1560 ms	244440 KB	Output is correct
2	Correct	1624 ms	242336 KB	Output is correct
3	Correct	1585 ms	236124 KB	Output is correct

Subtask #2

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	324 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct

Subtask #3

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	324 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct

Subtask #4

21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	324 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	380 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct

Subtask #5

26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	324 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	380 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	40 ms	5328 KB	Output is correct
15	Correct	40 ms	5192 KB	Output is correct
16	Correct	50 ms	5040 KB	Output is correct

Subtask #6

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1622 ms	205948 KB	Output is correct
2	Correct	1609 ms	223000 KB	Output is correct
3	Correct	1568 ms	217664 KB	Output is correct

Subtask #7

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1560 ms	244440 KB	Output is correct
2	Correct	1624 ms	242336 KB	Output is correct
3	Correct	1585 ms	236124 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	324 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	1 ms	380 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	1 ms	332 KB	Output is correct
17	Correct	40 ms	5328 KB	Output is correct
18	Correct	40 ms	5192 KB	Output is correct
19	Correct	50 ms	5040 KB	Output is correct
20	Correct	1622 ms	205948 KB	Output is correct
21	Correct	1609 ms	223000 KB	Output is correct
22	Correct	1568 ms	217664 KB	Output is correct
23	Execution timed out	2031 ms	246288 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-