oj.uz

Submission #198137

# Submission time Handle Problem Language Result Execution time Memory
198137 2020-01-24T19:44:20 Z popovicirobert Lightning Rod (NOI18_lightningrod) C++14
66 / 100
 2000 ms 242096 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];

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);

    cin >> n;

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

    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
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2060 ms 185228 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 504 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 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 504 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

Subtask #4
21.0 / 21.0

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

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 1 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 504 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 3 ms 376 KB Output is correct
12 Correct 3 ms 380 KB Output is correct
13 Correct 3 ms 504 KB Output is correct
14 Correct 61 ms 6136 KB Output is correct
15 Correct 61 ms 6036 KB Output is correct
16 Correct 53 ms 5752 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2070 ms 242096 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2060 ms 185228 KB Time limit exceeded
2 Halted 0 ms 0 KB -