oj.uz

Submission #496805

# Submission time Handle Problem Language Result Execution time Memory
496805 2021-12-22T04:42:53 Z SirCovidThe19th Lightning Rod (NOI18_lightningrod) C++17
66 / 100
 2000 ms 231916 KB 
#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(){
    int n; cin >> n; 
    bool covered[n] = {}; pii A[n]; set<pii> S;

    FOR(i, 0, n){
        cin >> A[i].f >> A[i].s;
        while (!S.empty() and prev(S.end())->f >= A[i].f - A[i].s){
            covered[prev(S.end())->s] = 1;
            S.erase(prev(S.end()));
        }
        S.insert({A[i].f - A[i].s, i});
    }
    S.clear();
    for (int i = n - 1; ~i; i--) if (!covered[i]){
        while (!S.empty() and S.begin()->f <= A[i].f + A[i].s){
            covered[S.begin()->s] = 1;
            S.erase(S.begin());
        }
        S.insert({A[i].f + A[i].s, i});
    }
    cout<<n - accumulate(covered, covered + n, 0)<<endl;
}

Subtask #1
0 / 4.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 268 KB Output is correct
2 Correct 0 ms 272 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 296 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 0 ms 208 KB Output is correct
7 Correct 0 ms 208 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 268 KB Output is correct
2 Correct 0 ms 272 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 296 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 0 ms 208 KB Output is correct
7 Correct 0 ms 208 KB Output is correct
8 Correct 0 ms 296 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 208 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 268 KB Output is correct
2 Correct 0 ms 272 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 296 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 0 ms 208 KB Output is correct
7 Correct 0 ms 208 KB Output is correct
8 Correct 0 ms 296 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 2 ms 300 KB Output is correct
12 Correct 2 ms 336 KB Output is correct
13 Correct 3 ms 352 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 268 KB Output is correct
2 Correct 0 ms 272 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 296 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 0 ms 208 KB Output is correct
7 Correct 0 ms 208 KB Output is correct
8 Correct 0 ms 296 KB Output is correct
9 Correct 0 ms 208 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 2 ms 300 KB Output is correct
12 Correct 2 ms 336 KB Output is correct
13 Correct 3 ms 352 KB Output is correct
14 Correct 182 ms 5492 KB Output is correct
15 Correct 150 ms 5296 KB Output is correct
16 Correct 160 ms 9900 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2033 ms 203564 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 2081 ms 231916 KB Time limit exceeded
2 Halted 0 ms 0 KB -