Submission #1130231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130231		fzyzzz_z	Tower (JOI24_tower)	C++20	25 / 100	485 ms	33484 KiB

Main

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

using ll = long long; 

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

void tleassert(bool b) {
    if (b) return; 
    ll c = 0; 
    for (int i = 0; i < 2043294832; ++i) {
        for (int j = 34; j < 43898943; ++j) {
            c += i; 
            c += 2 * i; 
            c %= j; 
        }
    }
    cout << c << '\n'; 
}

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;
    map<pair<ll, ll>, int> to; 
    int ind = 0; 
    st.insert(segs[0]); 
    to[segs[0]] = ind++; 
    for (int i = 1; i <= n; ++i) {
        ll yes = 2LL * 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}); 
            to[{yes, segs[i].second}] = ind++; 
        }
    }
    segs.clear(); 
    for (auto [x, y]: st) segs.emplace_back(x, y); 


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


    if (cb >= ca * d) {
        vector<ll> dp(ind, 1e9); 
        dp[0] = 0; 
        for (int i = 1; i < ind; ++i) {
            int lo = 0, hi = i - 1; 
            while (lo < hi) {
                int md = (lo + hi) / 2; 
                if (segs[i].first - d <= segs[md].second) {
                    hi = md; 
                } else {
                    lo = md + 1; 
                }
            }
            tleassert(segs[lo].first <= segs[i].first - d); 
            dp[i] = dp[lo + 1]; 
        }
        while (q--) {
            ll p; 
            cin >> p;   

            int i = can_reach(p); 
            if (i == -1) {
                cout << "-1\n"; 
            } else {
                cout << (dp[i] * cb + (p - d * dp[i]) * ca) << '\n'; 
            }
        }
    } else {
        assert(false); 
    }

}

Compilation message (stderr)

Main.cpp: In function 'void tleassert(bool)':
Main.cpp:14:20: warning: iteration 1073741824 invokes undefined behavior [-Waggressive-loop-optimizations]
   14 |             c += 2 * i;
      |                  ~~^~~
Main.cpp:11:23: note: within this loop
   11 |     for (int i = 0; i < 2043294832; ++i) {
      |                     ~~^~~~~~~~~~~~

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