답안 #496839

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
496839	2021-12-22T05:08:41 Z	SirCovidThe19th	Lightning Rod (NOI18_lightningrod)	C++17	100 / 100	1748 ms	233608 KB

lightningrod

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

#define FOR(i, x, y) for (int i = x; i < y; i++)
#define pii pair<int, int>
#define f first
#define s second

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 
    int n; cin >> n; 
    bool covered[n] = {}; pii A[n]; int H = -1; vector<pii> S;

    FOR(i, 0, n){
        cin >> A[i].f >> A[i].s;
        while (!S.empty() and S.back().f >= A[i].f - A[i].s){
            covered[S.back().s] = 1;
            S.pop_back();
        }
        if (A[i].f + A[i].s > H){ 
            S.push_back({A[i].f - A[i].s, i});
            H = max(H, A[i].f + A[i].s);
        }
    }
    cout<<S.size()<<endl;
}

Subtask #1

4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1527 ms	217756 KB	Output is correct
2	Correct	1559 ms	233608 KB	Output is correct
3	Correct	1477 ms	223972 KB	Output is correct

Subtask #2

7.0 / 7.0

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

Subtask #3

12.0 / 12.0

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

Subtask #4

21.0 / 21.0

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

Subtask #5

26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	0 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	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	1 ms	312 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	332 KB	Output is correct
14	Correct	44 ms	3564 KB	Output is correct
15	Correct	56 ms	3760 KB	Output is correct
16	Correct	35 ms	4780 KB	Output is correct

Subtask #6

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1535 ms	157072 KB	Output is correct
2	Correct	1479 ms	154196 KB	Output is correct
3	Correct	1671 ms	152096 KB	Output is correct

Subtask #7

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1527 ms	217756 KB	Output is correct
2	Correct	1559 ms	233608 KB	Output is correct
3	Correct	1477 ms	223972 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	0 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	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	0 ms	204 KB	Output is correct
13	Correct	1 ms	312 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	332 KB	Output is correct
17	Correct	44 ms	3564 KB	Output is correct
18	Correct	56 ms	3760 KB	Output is correct
19	Correct	35 ms	4780 KB	Output is correct
20	Correct	1535 ms	157072 KB	Output is correct
21	Correct	1479 ms	154196 KB	Output is correct
22	Correct	1671 ms	152096 KB	Output is correct
23	Correct	1724 ms	81140 KB	Output is correct
24	Correct	1748 ms	80736 KB	Output is correct
25	Correct	1638 ms	85560 KB	Output is correct