답안 #496830

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
496830	2021-12-22T05:01:59 Z	SirCovidThe19th	Lightning Rod (NOI18_lightningrod)	C++17	100 / 100	1918 ms	262144 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]; stack<pii> S;

    FOR(i, 0, n){
        cin >> A[i].f >> A[i].s;
        while (!S.empty() and S.top().f >= A[i].f - A[i].s){
            covered[S.top().s] = 1;
            S.pop();
        }
        S.push({A[i].f - A[i].s, i});
    }
    S = stack<pii>();
    for (int i = n - 1; ~i; i--) if (!covered[i]){
        while (!S.empty() and S.top().f <= A[i].f + A[i].s){
            covered[S.top().s] = 1;
            S.pop();
        }
        S.push({A[i].f + A[i].s, i});
    }
    cout<<n - accumulate(covered, covered + n, 0)<<endl;
}

Subtask #1

4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1532 ms	250460 KB	Output is correct
2	Correct	1559 ms	262144 KB	Output is correct
3	Correct	1564 ms	262144 KB	Output is correct

Subtask #2

7.0 / 7.0

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

Subtask #3

12.0 / 12.0

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

Subtask #4

21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 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	0 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	0 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	1 ms	204 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	1 ms	204 KB	Output is correct
2	Correct	0 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	0 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	0 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	1 ms	332 KB	Output is correct
13	Correct	1 ms	332 KB	Output is correct
14	Correct	37 ms	1936 KB	Output is correct
15	Correct	40 ms	1996 KB	Output is correct
16	Correct	36 ms	2880 KB	Output is correct

Subtask #6

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1523 ms	204540 KB	Output is correct
2	Correct	1559 ms	245348 KB	Output is correct
3	Correct	1514 ms	239460 KB	Output is correct

Subtask #7

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1532 ms	250460 KB	Output is correct
2	Correct	1559 ms	262144 KB	Output is correct
3	Correct	1564 ms	262144 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	0 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	0 ms	204 KB	Output is correct
9	Correct	0 ms	204 KB	Output is correct
10	Correct	0 ms	204 KB	Output is correct
11	Correct	0 ms	204 KB	Output is correct
12	Correct	0 ms	204 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	332 KB	Output is correct
16	Correct	1 ms	332 KB	Output is correct
17	Correct	37 ms	1936 KB	Output is correct
18	Correct	40 ms	1996 KB	Output is correct
19	Correct	36 ms	2880 KB	Output is correct
20	Correct	1523 ms	204540 KB	Output is correct
21	Correct	1559 ms	245348 KB	Output is correct
22	Correct	1514 ms	239460 KB	Output is correct
23	Correct	1918 ms	255576 KB	Output is correct
24	Correct	1841 ms	236744 KB	Output is correct
25	Correct	1771 ms	223204 KB	Output is correct