Submission #1021882

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021882		PurpleCrayon	Tower (JOI24_tower)	C++17	0 / 100	81 ms	16968 KiB

Main

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

#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 3e5+10, MOD = 1e9+7;
const ll INF = 1e18+10;
const int M = 1e6+10;

int n, q;
ll d, a, b;
pair<ll, ll> dead[N];
set<pair<ll, ll>> can;
ll dp[M];

bool is_dead(ll x) {
    int i = upper_bound(dead, dead + n, make_pair(x, INF)) - dead;
    return 0 <= i && i < n && dead[i].first <= x && x <= dead[i].second;
}

bool qry_can(ll x) {
    auto it = can.upper_bound(make_pair(x, INF));
    if (it != can.begin()) {
        --it;
        if (it->first <= x && x <= it->second)
            return true;
    }

    return false;
}

map<ll, ll> memo;
ll calc_small(ll x) {
    if (memo.count(x)) return memo[x];
    auto it = prev(can.upper_bound(make_pair(x, INF)));
    assert(it->first <= x && x <= it->second);
    ll ans = a * (x - it->first);
    if (x == it->first) {
        if (qry_can(x - 1)) {
            return memo[x] = a + calc_small(x - 1);
        } else {
            return memo[x] = b + calc_small(x - d);
        }
    } else {
        return memo[x] = ans + calc_small(it->first);
    }
}

void solve() {
    cin >> n >> q;
    cin >> d >> a >> b;
    for (int i = 0; i < n; i++) {
        ll l, r; cin >> l >> r;
        dead[i] = {l, r};
    }

    vector<pair<ll, ll>> alive;
    ll prv = -1;
    for (int i = 0; i < n; i++) {
        alive.emplace_back(prv + 1, dead[i].first - 1);
        prv = dead[i].second;
    }
    alive.emplace_back(prv + 1, INF);;

    can.insert(alive[0]);
    for (int i = 1; i < sz(alive); i++) {
        auto [l, r] = alive[i];
        if (qry_can(l - d)) {
            can.insert(alive[i]);
        } else {
            auto it = can.lower_bound(make_pair(l - d, -INF));
            if (it != can.end() && it->first + d <= r) {
                can.insert({it->first + d, r});
            }
        }
    }

    dp[0] = 0;
    for (int i = 1; i < M; i++) {
        dp[i] = INF;
        if (qry_can(i)) {
            if (a * d <= b) {
                if (qry_can(i - 1))
                    dp[i] = dp[i-1] + a;
                else
                    dp[i] = dp[i-d] + b;
            } else {
                if (qry_can(i - d))
                    dp[i] = dp[i-d] + b;
                else
                    dp[i] = dp[i-1] + a;
            }
        }
    }

    while (q--) {
        ll x; cin >> x;
        if (!qry_can(x)) {
            cout << -1 << '\n';
            continue;
        }

        if (a * d <= b) {
            // prefer little steps
            cout << calc_small(x) << '\n';
        } else if (x < M) {
            cout << dp[x] << '\n';
        } else {
            cout << x << '\n';
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
}

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