oj.uz

Submission #1021883

# Submission time Handle Problem Language Result Execution time Memory
1021883 2024-07-13T06:57:05 Z PurpleCrayon Tower (JOI24_tower) C++17
30 / 100
 620 ms 70844 KB 
#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 (x == 0) return 0;
    if (memo.count(x)) return memo[x];
    assert(qry_can(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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 8284 KB Output is correct
2 Correct 15 ms 8208 KB Output is correct
3 Correct 79 ms 11144 KB Output is correct
4 Correct 78 ms 11092 KB Output is correct
5 Correct 165 ms 17744 KB Output is correct
6 Correct 169 ms 17968 KB Output is correct
7 Correct 168 ms 18000 KB Output is correct
8 Correct 291 ms 30684 KB Output is correct
9 Correct 280 ms 30656 KB Output is correct
10 Correct 509 ms 46276 KB Output is correct
11 Correct 525 ms 45104 KB Output is correct
12 Correct 483 ms 46004 KB Output is correct
13 Correct 55 ms 19652 KB Output is correct
14 Correct 202 ms 24276 KB Output is correct
15 Correct 67 ms 18888 KB Output is correct
16 Correct 282 ms 33512 KB Output is correct
17 Correct 60 ms 19392 KB Output is correct
18 Correct 56 ms 19532 KB Output is correct
19 Correct 76 ms 16208 KB Output is correct
20 Correct 37 ms 10324 KB Output is correct
21 Correct 82 ms 16280 KB Output is correct
22 Correct 80 ms 17488 KB Output is correct
23 Correct 36 ms 10324 KB Output is correct
24 Correct 41 ms 11524 KB Output is correct
25 Correct 81 ms 16464 KB Output is correct
26 Correct 41 ms 11600 KB Output is correct
27 Correct 39 ms 10412 KB Output is correct
28 Correct 44 ms 11572 KB Output is correct
29 Correct 38 ms 10332 KB Output is correct
30 Correct 41 ms 11524 KB Output is correct

Subtask #2
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 8284 KB Output is correct
2 Correct 15 ms 8284 KB Output is correct
3 Incorrect 24 ms 8532 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 16468 KB Output is correct
2 Correct 76 ms 16464 KB Output is correct
3 Correct 30 ms 8784 KB Output is correct
4 Correct 562 ms 62656 KB Output is correct
5 Correct 538 ms 64704 KB Output is correct
6 Correct 553 ms 65732 KB Output is correct
7 Correct 599 ms 63676 KB Output is correct
8 Correct 556 ms 65984 KB Output is correct
9 Correct 618 ms 66668 KB Output is correct
10 Correct 566 ms 63224 KB Output is correct
11 Correct 614 ms 64192 KB Output is correct
12 Correct 575 ms 69568 KB Output is correct
13 Correct 620 ms 70844 KB Output is correct
14 Correct 180 ms 29476 KB Output is correct
15 Correct 134 ms 24768 KB Output is correct
16 Correct 128 ms 24252 KB Output is correct
17 Correct 546 ms 63416 KB Output is correct
18 Correct 528 ms 61340 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 8284 KB Output is correct
2 Correct 15 ms 8208 KB Output is correct
3 Correct 79 ms 11144 KB Output is correct
4 Correct 78 ms 11092 KB Output is correct
5 Correct 165 ms 17744 KB Output is correct
6 Correct 169 ms 17968 KB Output is correct
7 Correct 168 ms 18000 KB Output is correct
8 Correct 291 ms 30684 KB Output is correct
9 Correct 280 ms 30656 KB Output is correct
10 Correct 509 ms 46276 KB Output is correct
11 Correct 525 ms 45104 KB Output is correct
12 Correct 483 ms 46004 KB Output is correct
13 Correct 55 ms 19652 KB Output is correct
14 Correct 202 ms 24276 KB Output is correct
15 Correct 67 ms 18888 KB Output is correct
16 Correct 282 ms 33512 KB Output is correct
17 Correct 60 ms 19392 KB Output is correct
18 Correct 56 ms 19532 KB Output is correct
19 Correct 76 ms 16208 KB Output is correct
20 Correct 37 ms 10324 KB Output is correct
21 Correct 82 ms 16280 KB Output is correct
22 Correct 80 ms 17488 KB Output is correct
23 Correct 36 ms 10324 KB Output is correct
24 Correct 41 ms 11524 KB Output is correct
25 Correct 81 ms 16464 KB Output is correct
26 Correct 41 ms 11600 KB Output is correct
27 Correct 39 ms 10412 KB Output is correct
28 Correct 44 ms 11572 KB Output is correct
29 Correct 38 ms 10332 KB Output is correct
30 Correct 41 ms 11524 KB Output is correct
31 Correct 15 ms 8284 KB Output is correct
32 Correct 15 ms 8284 KB Output is correct
33 Incorrect 24 ms 8532 KB Output isn't correct
34 Halted 0 ms 0 KB -