답안 #667992

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
667992	2022-12-02T13:50:22 Z	bashkort	Lightning Rod (NOI18_lightningrod)	C++17	100 / 100	1582 ms	76200 KB

lightningrod

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 100000000;

int stk1[N], stk2[N], top = 0;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int x, y;
        cin >> x >> y;

        while (top > 0 && stk1[top - 1] >= x - y) {
            --top;
        }

        if (top == 0 || stk2[top - 1] < x + y) {
            stk1[top] = x - y, stk2[top] = x + y;
            top += 1;
        }
    }

    cout << top << '\n';

    return 0;
}

Subtask #1

4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1307 ms	76200 KB	Output is correct
2	Correct	1276 ms	75956 KB	Output is correct
3	Correct	1366 ms	73932 KB	Output is correct

Subtask #2

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 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	0 ms	212 KB	Output is correct

Subtask #3

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 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	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct

Subtask #4

21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 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	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	340 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	0 ms	212 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 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	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	340 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	37 ms	224 KB	Output is correct
15	Correct	36 ms	340 KB	Output is correct
16	Correct	31 ms	980 KB	Output is correct

Subtask #6

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1414 ms	49100 KB	Output is correct
2	Correct	1339 ms	49064 KB	Output is correct
3	Correct	1385 ms	47904 KB	Output is correct

Subtask #7

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1307 ms	76200 KB	Output is correct
2	Correct	1276 ms	75956 KB	Output is correct
3	Correct	1366 ms	73932 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 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	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	1 ms	340 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	37 ms	224 KB	Output is correct
18	Correct	36 ms	340 KB	Output is correct
19	Correct	31 ms	980 KB	Output is correct
20	Correct	1414 ms	49100 KB	Output is correct
21	Correct	1339 ms	49064 KB	Output is correct
22	Correct	1385 ms	47904 KB	Output is correct
23	Correct	1582 ms	580 KB	Output is correct
24	Correct	1568 ms	588 KB	Output is correct
25	Correct	1486 ms	3220 KB	Output is correct