oj.uz

Submission #198151

# Submission time Handle Problem Language Result Execution time Memory
198151 2020-01-24T21:37:58 Z popovicirobert Lightning Rod (NOI18_lightningrod) C++14
80 / 100
 2000 ms 262144 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define uint unsigned int


using namespace std;

const int MAXN = (int) 1e7 + 5;

int x[MAXN + 1], y[MAXN + 1];
int stk[MAXN + 1], sp[MAXN + 1];

inline int getnr() {
    char ch = getchar();
    int ans = 0;
    while(!isdigit(ch)) {
        ch = getchar();
    }
    while(isdigit(ch)) {
        ans = ans * 10 + ch - '0';
        ch = getchar();
    }
    return ans;
}

int main() {
#ifdef HOME
    ifstream cin("A.in");
    ofstream cout("A.out");
#endif
    int i, n;
    //ios::sync_with_stdio(false);
    //cin.tie(0), cout.tie(0);


    n = getnr();

    for(i = 1; i <= n; i++) {
        x[i] = getnr();
        y[i] = getnr();
    }

    stk[0] = -1;

    int sz = 0;
    for(i = 1; i <= n; i++) {
        while(sz > 0 && x[i] - x[stk[sz]] <= y[i] - y[stk[sz]]) {
            sz--;
        }
        sp[stk[sz] + 1]++;
        stk[++sz] = i;
    }

    sz = 0, stk[0] = n + 1;
    for(i = n; i >= 1; i--) {
        while(sz > 0 && x[stk[sz]] - x[i] <= y[i] - y[stk[sz]]) {
            sz--;
        }
        sp[stk[sz]]--;
        stk[++sz] = i;
    }

    int ans = 0;
    for(i = 1; i <= n; i++) {
        sp[i] += sp[i - 1];
        ans += (sp[i] == 1);
    }

    cout << ans;

    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1816 ms 175688 KB Output is correct
2 Correct 1825 ms 262144 KB Output is correct
3 Correct 1790 ms 256764 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 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 376 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 380 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 376 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 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 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 376 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 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 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 376 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 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 3 ms 376 KB Output is correct
14 Correct 62 ms 6156 KB Output is correct
15 Correct 59 ms 6016 KB Output is correct
16 Correct 49 ms 5624 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1669 ms 171448 KB Output is correct
2 Correct 1682 ms 242132 KB Output is correct
3 Correct 1637 ms 234384 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1816 ms 175688 KB Output is correct
2 Correct 1825 ms 262144 KB Output is correct
3 Correct 1790 ms 256764 KB Output is correct
4 Correct 2 ms 380 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 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 376 KB Output is correct
12 Correct 2 ms 380 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 3 ms 376 KB Output is correct
15 Correct 3 ms 376 KB Output is correct
16 Correct 3 ms 376 KB Output is correct
17 Correct 62 ms 6156 KB Output is correct
18 Correct 59 ms 6016 KB Output is correct
19 Correct 49 ms 5624 KB Output is correct
20 Correct 1669 ms 171448 KB Output is correct
21 Correct 1682 ms 242132 KB Output is correct
22 Correct 1637 ms 234384 KB Output is correct
23 Execution timed out 2045 ms 192584 KB Time limit exceeded
24 Halted 0 ms 0 KB -