oj.uz

Submission #744004

# Submission time Handle Problem Language Result Execution time Memory
744004 2023-05-18T07:08:41 Z vjudge1 Lightning Rod (NOI18_lightningrod) C++17
100 / 100
 1691 ms 156524 KB 
#include<bits/stdc++.h>
using namespace std;

struct point
{
    int x,y;
};

int n;
vector<point> vec;
stack<point> st;
int cnt = 0;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for(int i=0;i<n;++i)
    {
        int a,b;
        cin >> a >> b;
        vec.push_back({a,b});
    }
    for(int i=0;i<n;++i)
    {
        while(!st.empty() && vec[i].y-st.top().y >= vec[i].x-st.top().x) st.pop();
        if(st.empty() || !(st.top().y-vec[i].y >= vec[i].x-st.top().x))
        {
//            cout << "add " << vec[i].x << " " << vec[i].y << '\n';
            st.push({vec[i].x,vec[i].y});
        }
    }
    cout << st.size();
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1540 ms 156524 KB Output is correct
2 Correct 1461 ms 156240 KB Output is correct
3 Correct 1444 ms 152248 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 316 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 2 ms 340 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 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 316 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 39 ms 3328 KB Output is correct
15 Correct 41 ms 3500 KB Output is correct
16 Correct 35 ms 3396 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1437 ms 132116 KB Output is correct
2 Correct 1494 ms 132752 KB Output is correct
3 Correct 1485 ms 132880 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1540 ms 156524 KB Output is correct
2 Correct 1461 ms 156240 KB Output is correct
3 Correct 1444 ms 152248 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 316 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 316 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 39 ms 3328 KB Output is correct
18 Correct 41 ms 3500 KB Output is correct
19 Correct 35 ms 3396 KB Output is correct
20 Correct 1437 ms 132116 KB Output is correct
21 Correct 1494 ms 132752 KB Output is correct
22 Correct 1485 ms 132880 KB Output is correct
23 Correct 1691 ms 132928 KB Output is correct
24 Correct 1682 ms 132944 KB Output is correct
25 Correct 1677 ms 133928 KB Output is correct