Submission #1130257

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130257		fzyzzz_z	Tower (JOI24_tower)	C++20	25 / 100	434 ms	33588 KiB

Main

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

using ll = long long; 

const ll A = 1000000000000LL; 

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, A); 
        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 {
        vector<ll> dp(ind, A); 
        vector<ll> f(ind, -1); 
        dp[0] = 0; 
        f[0] = (d <= segs[0].second ? d : -1); 

        for (int i = 1; i < ind; ++i) {
            ll last_pos = segs[i].first - d; 
            int last = can_reach(last_pos); 
            assert(last != -1); 


            ll ops = dp[last]; 
            // cout << "!" << i << ' ' << last << ' ' << dp[last] << '\n'; 
            if (f[last] != -1 && last_pos >= f[last]) {
                ops = dp[last] + 1LL + (last_pos - f[last]) / d; 
            }
            dp[i] = ops + 1; 
            // cout << ops + 1 << '\n'; 
            f[i] = segs[i].first + d; 
            if (f[last] != -1) {
                ll diff = (f[last] - last_pos) % d; 
                if (diff <= 0) diff += d; 
                

                if (last_pos + diff <= segs[last].second && last_pos + diff + d <= segs[i].second) {
                    f[i] = min(f[i], last_pos + diff + d); 
                }
            }

            if (last + 1 < i) {
                int lo = last + 1, hi = i - 1; 
                while (lo < hi) {
                    int md = (lo + hi) / 2; 
                    ll v = dp[md]; 

                    if (v == dp[i] || (v + 1 == dp[i] && f[md] != -1)) {
                        hi = md; 
                    } else {
                        lo = md + 1; 
                    }
                }
                if (dp[lo] == dp[i]) {
                    f[i] = min(f[i], segs[lo].first + d); 
                } else if (dp[lo] + 1 == dp[i] && f[lo] != -1) {
                    f[i] = min(f[i], f[lo] + d); 
                }
            }

            if (f[i] > segs[i].second) f[i] = -1; 

            // cout << segs[i].first << ' ' << segs[i].second << ' '  << dp[i] << " " << f[i] << '\n'; 
        }


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

            int i = can_reach(p); 
            if (i == -1) {
                cout << "-1\n"; 
            } else {
                ll ops = dp[i]; 
                if (f[i] != -1 && p >= f[i]) {
                    ops = dp[i] + 1LL + (p - f[i]) / d; 
                }
                cout << (ops * cb + (p - d * ops) * ca) << '\n'; 
            }
        }


        // 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