답안 #335367

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
335367	2020-12-12T05:45:30 Z	ncduy0303	Lightning Rod (NOI18_lightningrod)	C++17	100 / 100	1997 ms	90132 KB

lightningrod

#include <bits/stdc++.h>

using namespace std;

#define ar array
#define ll long long

const int MAX_N = 1e5 + 1;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LINF = 1e18;

inline int readInt() {
    int x = 0;
    char ch = getchar_unlocked();
    while (ch < '0' || ch > '9') ch = getchar_unlocked();
    while ('0' <= ch && ch <= '9') {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar_unlocked();
    }
    return x;
}

void solve() {
    // int n = readInt();
    int n; cin >> n;
    stack<ar<int,2>> st;
    while (n--) { // increasing x
        // int x = readInt(), y = readInt();
        int x, y; cin >> x >> y;
        bool add = true;
        while (st.size()) { 
            auto [tx, ty] = st.top();
            if (x + y <= tx + ty) { // (tx, ty) covers (x, y) 
                add = false;
                break;
            }
            if (x - y <= tx - ty) st.pop(); // (x, y) covers (tx, ty)
            else break;
        }
        if (add) st.push({x, y});
    }
    cout << st.size() << "\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    int tc = 1;
    // cin >> tc;
    for (int t = 1; t <= tc; t++) {
        // cout << "Case #" << t  << ": ";
        solve();
    }
}

Subtask #1

4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1694 ms	90132 KB	Output is correct
2	Correct	1700 ms	89924 KB	Output is correct
3	Correct	1649 ms	87596 KB	Output is correct

Subtask #2

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct

Subtask #3

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	492 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct

Subtask #4

21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	492 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct

Subtask #5

26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	492 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	44 ms	3960 KB	Output is correct
15	Correct	47 ms	3692 KB	Output is correct
16	Correct	40 ms	3820 KB	Output is correct

Subtask #6

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1726 ms	60184 KB	Output is correct
2	Correct	1740 ms	60272 KB	Output is correct
3	Correct	1675 ms	58508 KB	Output is correct

Subtask #7

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1694 ms	90132 KB	Output is correct
2	Correct	1700 ms	89924 KB	Output is correct
3	Correct	1649 ms	87596 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	492 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	1 ms	364 KB	Output is correct
17	Correct	44 ms	3960 KB	Output is correct
18	Correct	47 ms	3692 KB	Output is correct
19	Correct	40 ms	3820 KB	Output is correct
20	Correct	1726 ms	60184 KB	Output is correct
21	Correct	1740 ms	60272 KB	Output is correct
22	Correct	1675 ms	58508 KB	Output is correct
23	Correct	1997 ms	15480 KB	Output is correct
24	Correct	1964 ms	11372 KB	Output is correct
25	Correct	1861 ms	9580 KB	Output is correct