답안 #541688

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
541688	2022-03-24T07:44:28 Z	cristi_a	Lightning Rod (NOI18_lightningrod)	C++17	80 / 100	2000 ms	262144 KB

lightningrod

#include <bits/stdc++.h>
using namespace std;

bool cover(pair<int,int> a, pair<int,int> b) {
    return abs(a.first-b.first) <= a.second - b.second;
}

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

    int n; cin >> n;
    vector<pair<int,int>> v(n);
    for(int i=0; i<n; i++) cin >> v[i].first >> v[i].second;
    sort(v.begin(), v.end());
    stack<pair<int,int>> st;
    for(int i=0; i<n; i++) {
        while(!st.empty() and cover(v[i], st.top())) st.pop();
        if(st.empty()) st.emplace(v[i]);
        else if(!cover(st.top(), v[i])) st.emplace(v[i]);
    }
    cout << st.size();
    return 0;
}

Subtask #1

4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1766 ms	262144 KB	Output is correct
2	Correct	1823 ms	262144 KB	Output is correct
3	Correct	1724 ms	260388 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	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	320 KB	Output is correct
6	Correct	1 ms	324 KB	Output is correct
7	Correct	1 ms	212 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	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	320 KB	Output is correct
6	Correct	1 ms	324 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	320 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	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	320 KB	Output is correct
6	Correct	1 ms	324 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	320 KB	Output is correct
11	Correct	1 ms	380 KB	Output is correct
12	Correct	1 ms	376 KB	Output is correct
13	Correct	1 ms	336 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	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	320 KB	Output is correct
6	Correct	1 ms	324 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	320 KB	Output is correct
11	Correct	1 ms	380 KB	Output is correct
12	Correct	1 ms	376 KB	Output is correct
13	Correct	1 ms	336 KB	Output is correct
14	Correct	45 ms	5340 KB	Output is correct
15	Correct	45 ms	5196 KB	Output is correct
16	Correct	49 ms	5180 KB	Output is correct

Subtask #6

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1782 ms	225680 KB	Output is correct
2	Correct	1752 ms	225404 KB	Output is correct
3	Correct	1652 ms	219928 KB	Output is correct

Subtask #7

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1766 ms	262144 KB	Output is correct
2	Correct	1823 ms	262144 KB	Output is correct
3	Correct	1724 ms	260388 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	320 KB	Output is correct
9	Correct	1 ms	324 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	320 KB	Output is correct
14	Correct	1 ms	380 KB	Output is correct
15	Correct	1 ms	376 KB	Output is correct
16	Correct	1 ms	336 KB	Output is correct
17	Correct	45 ms	5340 KB	Output is correct
18	Correct	45 ms	5196 KB	Output is correct
19	Correct	49 ms	5180 KB	Output is correct
20	Correct	1782 ms	225680 KB	Output is correct
21	Correct	1752 ms	225404 KB	Output is correct
22	Correct	1652 ms	219928 KB	Output is correct
23	Execution timed out	2023 ms	245972 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-