Submission #1021876

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021876		PurpleCrayon	Tower (JOI24_tower)	C++17	30 / 100	286 ms	35524 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;
}

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 (x < M)
            cout << (dp[x] >= INF ? -1 : dp[x]) << '\n';
        else
            cout << (qry_can(x) ? x : -1) << '\n';
    }
}

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

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