oj.uz

Submission #621270

# Submission time Handle Problem Language Result Execution time Memory
621270 2022-08-03T16:13:29 Z PoonYaPat Lightning Rod (NOI18_lightningrod) C++14
80 / 100
 2000 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

const int MX=10000005;
int n,a[MX],b[MX],pre[MX],pos[MX];
stack<int> st;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for (int i=1; i<=n; ++i) {
        int x,y;
        cin>>x>>y;
        a[i]=x-y;
        b[i]=x+y;
    }

    for (int i=1; i<=n; ++i) {
        int idx=i-1;
        while (a[i]<=a[idx] && idx>=1) idx=pre[idx];
        pre[i]=idx;
    }

    for (int i=n; i>=1; --i) {
        int idx=i+1;
        while (b[i]>=b[idx] && idx<=n) idx=pos[idx];
        pos[i]=idx;
    }

    st.push(1);
    for (int i=2; i<=n; ++i) {
            //consider point i
        int k=st.top();
        if (pos[k]<=i) {
                //push rod at point i
            while (!st.empty() && pre[i]<=pre[st.top()]) st.pop();
            st.push(i);
        }
    }
    cout<<st.size();
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1364 ms 191936 KB Output is correct
2 Correct 1350 ms 191332 KB Output is correct
3 Correct 1322 ms 185992 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 352 KB Output is correct
13 Correct 1 ms 340 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 352 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 50 ms 6716 KB Output is correct
15 Correct 40 ms 6640 KB Output is correct
16 Correct 38 ms 6216 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1422 ms 181792 KB Output is correct
2 Correct 1504 ms 262144 KB Output is correct
3 Correct 1439 ms 262144 KB Output is correct

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1364 ms 191936 KB Output is correct
2 Correct 1350 ms 191332 KB Output is correct
3 Correct 1322 ms 185992 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 352 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 50 ms 6716 KB Output is correct
18 Correct 40 ms 6640 KB Output is correct
19 Correct 38 ms 6216 KB Output is correct
20 Correct 1422 ms 181792 KB Output is correct
21 Correct 1504 ms 262144 KB Output is correct
22 Correct 1439 ms 262144 KB Output is correct
23 Correct 1991 ms 262144 KB Output is correct
24 Execution timed out 2062 ms 262144 KB Time limit exceeded
25 Halted 0 ms 0 KB -