Submission #1130228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130228		fzyzzz_z	Tower (JOI24_tower)	C++20	25 / 100	269 ms	20400 KiB

Main

#include <bits/stdc++.h>
using namespace std; 

using ll = long long; 

const ll A = 1'000'000'000'000LL; 

int32_t main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(0); 

    int n, q; 
    cin >> n >> q; 
    ll d, ca, cb; 
    cin >> d >> ca >> cb; 
    vector<ll> v(2 * n + 2); 
    v[0] = 0; 
    v[2 * n + 1] = A; 
    for (int i = 1; i <= 2 * n; ++i) {
        cin >> v[i]; 
        if (i % 2) v[i]--; 
        else v[i]++; 
    }
    vector<pair<ll, ll>> segs; 
    for (int i = 0; i <= n; ++i) {
        segs.emplace_back(v[2 * i], v[2 * i + 1]); 
    }
    set<pair<ll, ll>> st; 
    st.insert(segs[0]); 
    for (int i = 1; i <= n; ++i) {
        ll yes = 2 * A; 
        auto it = st.lower_bound({segs[i].first - d, 0}); 
        if (it != st.end()) {
            yes = min(yes, (*it).first + d); 
        }
        if (it != st.begin()) {
            it--; 
            if (segs[i].first - d <= (*it).second) {
                yes = min(yes, segs[i].first); 
            }
        }

        if (yes <= segs[i].second) {
            st.insert({yes, segs[i].second}); 
        }
    }


    auto can_reach = [&] (ll p) -> bool {
        auto it = st.lower_bound({p + 1, -1});
        if (it != st.begin()) {
            it--; 
            auto [l, r] = *it; 
            return l <= p && p <= r; 
        }
        return false; 
    }; 

    while (q--) {
        ll p; 
        cin >> p; 

        // cout << "? " << " " << p << '\n'; 

        cout << (can_reach(p) ? p : -1LL) << '\n'; 
    }
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 38
• Subtask 3: 25 / 25
• Subtask 4: 0 / 32