oj.uz

Submission #743789

# Submission time Handle Problem Language Result Execution time Memory
743789 2023-05-18T01:53:59 Z vjudge1 Lightning Rod (NOI18_lightningrod) C++17
100 / 100
 491 ms 205836 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long

bool check(ll x1, ll x2, ll y1, ll y2)
{
    return abs(x1 - x2) <= y1 - y2;
}

inline void read(long long &x)
{
    x = 0;
    char ch = getchar_unlocked();
    while (ch & 16)
    {
        x = (x << 3) + (x << 1) + (ch & 15);
        ch = getchar_unlocked();
    }
}

int main()
{
    ll n;
    ll a, b;
    stack<pair<ll, ll>> st;
    read(n);
    for (int i = 0; i < n; ++i)
    {
        read(a);
        read(b);
        if (!st.empty() && check(st.top().first, a, st.top().second, b)) // old cover new
        {
            continue;
        }
        while (!st.empty() && check(a, st.top().first, b, st.top().second)) // new cover old
        {
            st.pop();
        }
        st.push({a,b});
    }
    cout << st.size();
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 182032 KB Output is correct
2 Correct 342 ms 205836 KB Output is correct
3 Correct 333 ms 198804 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 0 ms 212 KB Output is correct
3 Correct 0 ms 296 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 212 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 0 ms 212 KB Output is correct
3 Correct 0 ms 296 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 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 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 0 ms 212 KB Output is correct
3 Correct 0 ms 296 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 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 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 0 ms 212 KB Output is correct
3 Correct 0 ms 296 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 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 13 ms 3060 KB Output is correct
15 Correct 12 ms 2888 KB Output is correct
16 Correct 13 ms 4292 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 122836 KB Output is correct
2 Correct 328 ms 157592 KB Output is correct
3 Correct 304 ms 159092 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 182032 KB Output is correct
2 Correct 342 ms 205836 KB Output is correct
3 Correct 333 ms 198804 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 296 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 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 13 ms 3060 KB Output is correct
18 Correct 12 ms 2888 KB Output is correct
19 Correct 13 ms 4292 KB Output is correct
20 Correct 297 ms 122836 KB Output is correct
21 Correct 328 ms 157592 KB Output is correct
22 Correct 304 ms 159092 KB Output is correct
23 Correct 491 ms 75220 KB Output is correct
24 Correct 398 ms 72320 KB Output is correct
25 Correct 379 ms 73108 KB Output is correct