oj.uz

Submission #522759

# Submission time Handle Problem Language Result Execution time Memory
522759 2022-02-05T16:14:39 Z nhphucqt Lightning Rod (NOI18_lightningrod) C++17
100 / 100
 1760 ms 227808 KB 
#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

	scanf("%d", &numPoint);
	for (int i = 0; i < numPoint; ++i) {
		scanf("%d%d", &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;
		}
	}
	printf("%d", sz);
	return 0;
}

Compilation message

lightningrod.cpp: In function 'int main()':
lightningrod.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |  scanf("%d", &numPoint);
      |  ~~~~~^~~~~~~~~~~~~~~~~
lightningrod.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |   scanf("%d%d", &points[i].x, &points[i].y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1375 ms 152252 KB Output is correct
2 Correct 1419 ms 151808 KB Output is correct
3 Correct 1467 ms 147752 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
21.0 / 21.0

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

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 260 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 300 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 312 KB Output is correct
14 Correct 36 ms 2904 KB Output is correct
15 Correct 36 ms 3040 KB Output is correct
16 Correct 33 ms 3652 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1520 ms 127060 KB Output is correct
2 Correct 1492 ms 126972 KB Output is correct
3 Correct 1547 ms 123988 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1375 ms 152252 KB Output is correct
2 Correct 1419 ms 151808 KB Output is correct
3 Correct 1467 ms 147752 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 260 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 312 KB Output is correct
17 Correct 36 ms 2904 KB Output is correct
18 Correct 36 ms 3040 KB Output is correct
19 Correct 33 ms 3652 KB Output is correct
20 Correct 1520 ms 127060 KB Output is correct
21 Correct 1492 ms 126972 KB Output is correct
22 Correct 1547 ms 123988 KB Output is correct
23 Correct 1729 ms 71340 KB Output is correct
24 Correct 1760 ms 227808 KB Output is correct
25 Correct 1739 ms 211472 KB Output is correct