답안 #654648

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
654648	2022-11-01T05:11:26 Z	horiseun	Lightning Rod (NOI18_lightningrod)	C++11	100 / 100	1725 ms	175444 KB

lightningrod

#include <iostream>
#include <stack>
#include <tuple>
#include <algorithm>
using namespace std;

#define f first
#define s second

int n, x, y, cx, cy;
stack<pair<int, int>> s;

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x >> y;
        bool inc = true;
        while (s.size()) {
            tie(cx, cy) = s.top();
            if (x - cx <= cy - y) {
                inc = false;
                break;
            }
            if (x - cx <= y - cy) s.pop();
            else break;
        }
        if (inc) s.push({x, y});
    }

    cout << s.size() << "\n";


}

Subtask #1

4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1432 ms	166808 KB	Output is correct
2	Correct	1435 ms	165396 KB	Output is correct
3	Correct	1377 ms	159204 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	324 KB	Output is correct
3	Correct	1 ms	316 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	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	324 KB	Output is correct
3	Correct	1 ms	316 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	316 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 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	324 KB	Output is correct
3	Correct	1 ms	316 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	316 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	2 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	328 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	324 KB	Output is correct
3	Correct	1 ms	316 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	316 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	2 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	328 KB	Output is correct
14	Correct	39 ms	3880 KB	Output is correct
15	Correct	41 ms	3632 KB	Output is correct
16	Correct	35 ms	3708 KB	Output is correct

Subtask #6

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1414 ms	121104 KB	Output is correct
2	Correct	1388 ms	120568 KB	Output is correct
3	Correct	1454 ms	117068 KB	Output is correct

Subtask #7

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1432 ms	166808 KB	Output is correct
2	Correct	1435 ms	165396 KB	Output is correct
3	Correct	1377 ms	159204 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	324 KB	Output is correct
6	Correct	1 ms	316 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	316 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	2 ms	340 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	328 KB	Output is correct
17	Correct	39 ms	3880 KB	Output is correct
18	Correct	41 ms	3632 KB	Output is correct
19	Correct	35 ms	3708 KB	Output is correct
20	Correct	1414 ms	121104 KB	Output is correct
21	Correct	1388 ms	120568 KB	Output is correct
22	Correct	1454 ms	117068 KB	Output is correct
23	Correct	1715 ms	175444 KB	Output is correct
24	Correct	1725 ms	152276 KB	Output is correct
25	Correct	1651 ms	132240 KB	Output is correct