oj.uz

Submission #1049615

# Submission time Handle Problem Language Result Execution time Memory
1049615 2024-08-09T02:23:11 Z Whisper Lightning Rod (NOI18_lightningrod) C++17
100 / 100
 1132 ms 262144 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define int long long
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (b); i >= (a); i --)
#define REP(i, a) for (int i = 0; i < (a); ++i)
#define REPD(i, a) for (int i = (a) - 1; i >= 0; --i)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)


constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

/*
    Phu Trong from Nguyen Tat Thanh High School for gifted student
*/

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
int numHouse;

#define MAX                 10000005


pair<int, int> P[MAX];

bool cover(pair<int, int> i, pair<int, int> j){
    return abs(i.first - j.first) <= i.second - j.second;
}
void process(void){
    cin >> numHouse;
    for (int i = 1; i <= numHouse; ++i) {
        cin >> P[i].first >> P[i].second;
    }
    stack<int> st;

    for (int i = 1; i <= numHouse; ++i){
        while(st.size() && cover(P[i], P[st.top()])) st.pop();

        if (st.empty() || !cover(P[st.top()], P[i])){
            st.push(i);
        }
    }
    cout << (int)st.size();
}
signed main(){
    #define name "Whisper"
    cin.tie(nullptr) -> sync_with_stdio(false);
    //freopen(name".inp", "r", stdin);
    //freopen(name".out", "w", stdout);
    process();
    return (0 ^ 0);
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 889 ms 262144 KB Output is correct
2 Correct 904 ms 262144 KB Output is correct
3 Correct 901 ms 262144 KB Output is correct

Subtask #2
7.0 / 7.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
21.0 / 21.0

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

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 484 KB Output is correct
14 Correct 22 ms 6916 KB Output is correct
15 Correct 25 ms 6748 KB Output is correct
16 Correct 20 ms 8008 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 948 ms 262144 KB Output is correct
2 Correct 932 ms 262144 KB Output is correct
3 Correct 890 ms 262144 KB Output is correct

Subtask #7
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 889 ms 262144 KB Output is correct
2 Correct 904 ms 262144 KB Output is correct
3 Correct 901 ms 262144 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 484 KB Output is correct
17 Correct 22 ms 6916 KB Output is correct
18 Correct 25 ms 6748 KB Output is correct
19 Correct 20 ms 8008 KB Output is correct
20 Correct 948 ms 262144 KB Output is correct
21 Correct 932 ms 262144 KB Output is correct
22 Correct 890 ms 262144 KB Output is correct
23 Correct 1132 ms 262144 KB Output is correct
24 Correct 1049 ms 262144 KB Output is correct
25 Correct 987 ms 262144 KB Output is correct