oj.uz

Submission #94544

# Submission time Handle Problem Language Result Execution time Memory
94544 2019-01-20T07:36:33 Z FutymyClone Lightning Rod (NOI18_lightningrod) C++14
100 / 100
 1412 ms 157152 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e7 + 5;

int n;
stack <pair <int, int> > st;

int readInt(){
    char c;
    int ans = 0;
    while (1) {
        c = getchar();
        if (c == ' ' || c == '\n') return ans;
        ans = (ans << 3) + (ans << 1) + (c - '0');
    }
}

int main(){
    n = readInt();
    for (int i = 1; i <= n; i++) {
        int x, y;
        x = readInt(); y = readInt();

        bool ok = true;
        while (!st.empty()) {
            if (x - st.top().first <= st.top().second - y) {
                ok = false;
                break;
            }

            if (x - st.top().first <= y - st.top().second) st.pop();
            else break;
        }

        if (ok) st.push({x, y});
    }

    printf("%d", (int)st.size());
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 977 ms 82892 KB Output is correct
2 Correct 979 ms 82716 KB Output is correct
3 Correct 936 ms 80348 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 252 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 252 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 252 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 31 ms 3832 KB Output is correct
15 Correct 30 ms 3676 KB Output is correct
16 Correct 26 ms 3704 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 886 ms 53972 KB Output is correct
2 Correct 885 ms 53884 KB Output is correct
3 Correct 873 ms 52476 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 977 ms 82892 KB Output is correct
2 Correct 979 ms 82716 KB Output is correct
3 Correct 936 ms 80348 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 252 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 31 ms 3832 KB Output is correct
18 Correct 30 ms 3676 KB Output is correct
19 Correct 26 ms 3704 KB Output is correct
20 Correct 886 ms 53972 KB Output is correct
21 Correct 885 ms 53884 KB Output is correct
22 Correct 873 ms 52476 KB Output is correct
23 Correct 1412 ms 31836 KB Output is correct
24 Correct 1294 ms 157152 KB Output is correct
25 Correct 1196 ms 137008 KB Output is correct