답안 #538833

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
538833	2022-03-17T21:23:34 Z	four_specks	Lightning Rod (NOI18_lightningrod)	C++17	100 / 100	1834 ms	262144 KB

lightningrod

#include <bits/stdc++.h>

using namespace std;

inline namespace
{
} // namespace

struct Point
{
    long x, y;

    bool covers(const Point &p) const { return abs(x - p.x) <= y - p.y; }
};

void solve()
{
    int n;
    cin >> n;

    stack<Point> st;
    for (int i = 0; i < n; i++)
    {
        Point pt;
        cin >> pt.x >> pt.y;

        while (!st.empty() && pt.covers(st.top()))
            st.pop();
        if (st.empty() || !st.top().covers(pt))
            st.push(pt);
    }

    cout << (int)st.size() << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);

    solve();

    return 0;
}

Subtask #1

4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1514 ms	262144 KB	Output is correct
2	Correct	1513 ms	262144 KB	Output is correct
3	Correct	1452 ms	262144 KB	Output is correct

Subtask #2

7.0 / 7.0

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

Subtask #3

12.0 / 12.0

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

Subtask #4

21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	316 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	316 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct

Subtask #5

26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	316 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	316 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	40 ms	3876 KB	Output is correct
15	Correct	48 ms	3624 KB	Output is correct
16	Correct	36 ms	4320 KB	Output is correct

Subtask #6

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1539 ms	198616 KB	Output is correct
2	Correct	1482 ms	198716 KB	Output is correct
3	Correct	1409 ms	193736 KB	Output is correct

Subtask #7

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1514 ms	262144 KB	Output is correct
2	Correct	1513 ms	262144 KB	Output is correct
3	Correct	1452 ms	262144 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	316 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	316 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	40 ms	3876 KB	Output is correct
18	Correct	48 ms	3624 KB	Output is correct
19	Correct	36 ms	4320 KB	Output is correct
20	Correct	1539 ms	198616 KB	Output is correct
21	Correct	1482 ms	198716 KB	Output is correct
22	Correct	1409 ms	193736 KB	Output is correct
23	Correct	1800 ms	175648 KB	Output is correct
24	Correct	1834 ms	157080 KB	Output is correct
25	Correct	1700 ms	143056 KB	Output is correct