Blackjack#12323

Blackjack (Çözgüdiň düşündirişi)

Author of the problem:	Anton Perebiynis (Pcheloveks)
Prepared by:	Anton Perebiynis (Pcheloveks)
Analysis:	Anton Perebiynis (Pcheloveks)

Solution

Assume we have chosen a segment $[L, R]$ of length $l e n = R - L + 1$ len = R - L + 1. Then there are two possible cases for the distribution of aces: if $l e n \geq k_{L}$ len \geq k_L and if $l e n < k_{L}$ len < k_L.

$Case1$ : $l e n \geq k_{L}$ len \geq k_L

In this case, the result is equal to $\sum_{i = L}^{R} a_{i} + k_{L} * x_{L}$ \sum_{i = L}^{R} a_i + k_L * x_L. Using prefix sums, we can rewrite the formula as $p_{R} - p_{L - 1} + k_{L} * x_{L}$ p_R - p_{L - 1} + k_L * x_L, where $p_{i} = \sum_{j = 1}^{i} a_{j}$ p_i = \sum_{j = 1}^{i} a_j. It can be noted that this expression consists of two parts: one depends on $R$ — $p_{R}$ p_R, the other depends only on $L$ — $- p_{L - 1} + k_{L} * x_{L}$ -p_{L - 1} + k_L * x_L.

Thus, fixing the right boundary $R$ , we obtain a formula for the maximum result among all segments ending at point $R$ : $p_{R} + max_{R - L + 1 \geq k_{L}} (- p_{L - 1} + k_{L} * x_{L})$ p_R + \max_{R - L + 1 \geq k_L}(-p_{L - 1} + k_L * x_L). For a fixed $L$ , this condition holds for all $R \geq L + k_{L} - 1$ R \geq L + k_L - 1.

Therefore, iterating over $R$ from left to right, we will add the event of "activation" of the corresponding $L$ at the moment $L + k_{L} - 1$ L + k_L - 1 and maintain the maximum values of $- p_{L - 1} + k_{L} * x_{L}$ -p_{L - 1} + k_L * x_L among all active $L$ .

$Case2 :$ $l e n < k_{L}$ len < k_L

In this case, the result is equal to $\sum_{i = L}^{R} a_{i} + (R - L + 1) * x_{L}$ \sum_{i = L}^{R} a_i + (R - L + 1) * x_L. We can rewrite the formula using prefix sums:

$p_{R} - p_{L - 1} + (R - L + 1) * x_{L} = p_{R} - p_{L - 1} + x_{L} * R + x_{L} * (L - 1)$ p_R - p_{L - 1} + (R - L + 1) * x_L = p_R - p_{L - 1} + x_L * R + x_L * (L - 1).

Fixing $R$ and factoring out the parts that do not depend on $L$ :

$max_{R - L + 1 < k_{L}} (p_{R} - p_{L - 1} + x_{L} * R + x_{L} * (L - 1)) = p_{R} + max_{R - L + 1 < k_{L}} (x_{L} * R + x_{L} * (L - 1) - p_{L - 1})$ \max_{R - L + 1 < k_L}(p_R - p_{L - 1} + x_L * R + x_L * (L - 1)) = p_R + \max_{R - L + 1 < k_L}(x_L * R + x_L * (L - 1) - p_{L - 1}).

It can be seen that the dependence of the expression under the maximum on $R$ is linear and has the form $y = k * R + b$ y = k * R + b, where $k = x_{L}$ k = x_L and $b = x_{L} * (L - 1) - p_{L - 1}$ b = x_L * (L - 1) - p_{L - 1}.

Thus, we obtain a classical problem of finding the maximum among linear functions, which is solved using the Convex Hull Trick method, with the distinction that each linear function exists only for certain values of $R$ .

For a fixed $L$ , this function exists only for $R \in [L, L + k_{L} - 1)$ R \in [L, L + k_L - 1).

To correctly handle such constraints, we will use a segment tree. Each linear function is added to all nodes of the tree that completely cover the corresponding interval $[L, L + k_{L} - 1)$ [L, L + k_L - 1).

To obtain the answer for a specific $R$ , we descend the tree to the leaf corresponding to this point and take the maximum values among all Convex Hull Trick values stored in the nodes along this path.

For efficient implementation: we first store all requests to add lines and all requests to get the maximum, sort them, and add all lines to the corresponding nodes of the tree.

In each node, the values of $R$ for which requests occur will also be sorted. Since there are no additional constraints on the existence of lines within a single node, we can apply the standard Convex Hull Trick with monotonic queries.

$Complexity$

The time complexity of the algorithm is $O (N lo g_{2} N)$ O(N \log_{2} N), since each of the $N$ lines and each of the $N$ queries is added to $l o g_{2} N$ log_{2} N nodes of the segment tree, and processing in each node is done in linear time.

The first part of the algorithm (case $l e n \geq k_{L}$ len \geq k_L) runs in $O (N)$ .

Solution Code


#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <queue>
#include <bitset>
#include <map>
#include <vector>
#include <set>
#include <algorithm>

#define endl '\n'

using namespace std;

FILE* stream;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ld, ld > pdd;
const long long DIM = 500007;
const ld eps = 1e-12;
const long long INF = 1e18;
const long long Bsize = 450;
const int mod = 998244353;
const long long NUMSZ = 500;

struct line {
    ll k, b;

    line() {
        k = 0;
        b = 0;
    }

    line(ll k_, ll b_) {
        k = k_;
        b = b_;
    }

    ll get(ll x) {
        return (ll)k * (ll)x + (ll)b;
    }
};

ll intersection(const line& l1, const line& l2) {
    ll a = l2.b - l1.b;
    ll b = l1.k - l2.k;

    return a / b - ((a ^ b) < 0 && a % b);
}


class convexHull {
public:

    void init(int sz) {
        d.clear();
        d.resize(2 * sz + 5);
        L = sz;
        R = sz;
    }
    void add(line l) {
        if (R - L > 0 && d[R - 1].k == l.k) {
            if (d[R - 1].b >= l.b) return;
            R--;
        }

        while (R - L > 1 &&
            intersection(d[R - 2], d[R - 1]) >= intersection(d[R - 2], l)) {
            R--;
        }
        d[R++] = l;
    }


    ll query(ll x) {
        if (R - L == 0) return -INF;
        while (R - L > 1 && intersection(d[L], d[L + 1]) <= x) {
            L++;
        }
        return d[L].get(x);
    }

    void clear() {
        d.clear();
    }

private:

    int L, R;
    vector < line > d;
};

ll res[DIM];

class convexHullTree {
public:

    void init(int sz_) {
        sz = sz_;
        T.resize(4 * sz + 7);
    }

    void addLine(int L, int R, line l) {
        addLine(0, 1, sz, L, R, l);
    }

    void addQuery(int pos, ll x) {
        addQuery(0, 1, sz, pos, x);
    }

    void proces() {
        convexHull c;
        for (auto ver : T) {
            c.init(2 * ver.l.size());
            for (auto l : ver.l) c.add(l);
            for (auto x : ver.x) {
                res[x] = max(res[x], c.query(x));
            }
            c.clear();
        }
    }

private:

    void addLine(int v, int tl, int tr, int L, int R, line l) {
        if (L <= tl && tr <= R) {
            T[v].l.push_back(l);
            return;
        }
        if (tl > R || tr < L) return;

        int tm = (tl + tr) >> 1;

        addLine(2 * v + 1, tl, tm, L, R, l);
        addLine(2 * v + 2, tm + 1, tr, L, R, l);
    }

    void addQuery(int v, int tl, int tr, int pos, ll x) {
        T[v].x.push_back(x);
        if (tl == tr) {
            return;
        }

        int tm = (tl + tr) >> 1;
        if (pos <= tm) {
            addQuery(2 * v + 1, tl, tm, pos, x);
        }
        else {
            addQuery(2 * v + 2, tm + 1, tr, pos, x);
        }
    }

    struct node {
        vector < line > l;
        vector < ll > x;
    };

    int sz;
    vector < node > T;
};

struct queryLine {
    line l;
    ll L, R;
};

bool cmp(queryLine l1, queryLine l2) {
    return l1.l.k < l2.l.k;
}

vector < queryLine > Lq;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#ifdef _DEBUG
    freopen_s(&stream, "input.txt", "r", stdin);
    freopen_s(&stream, "output.txt", "w", stdout);
#endif

    int n;
    cin >> n;

    vector < ll > a(n + 1), k(n + 1), x(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> k[i];
    for (int i = 1; i <= n; i++) cin >> x[i];

    vector < ll > p = a;
    for (int i = 1; i <= n; i++) {
        p[i] += p[i - 1];
        if (k[i] == 0) {
            k[i] = 1;
            x[i] = 0;
        }
    }

    ll ans = -1e18;
    ll mxExp = -INF;

    vector < ll > events(n + 1, -INF);

    for (int i = 1; i <= n; i++) {
        if(i + k[i] - 1 <= n) events[i + k[i] - 1] = max(events[i + k[i] - 1], -p[i - 1] + k[i] * x[i]);
        Lq.push_back({ {x[i], -(ll)(i - 1) * x[i] - p[i - 1]}, i, i + k[i] - 1 });

        mxExp = max(mxExp, events[i]);

        ans = max(ans, mxExp + p[i]);
    }

    convexHullTree t;
    t.init(n);

    sort(Lq.begin(), Lq.end(), cmp);

    for (auto x : Lq) {
        if (x.L > x.R) continue;
        t.addLine(x.L, x.R, x.l);
    }
    for (int i = 1; i <= n; i++) {
        t.addQuery(i, i);
    }

    for (int i = 1; i <= n; i++) res[i] = -INF;
    t.proces();

    for (int i = 1; i <= n; i++) {
        ans = max(ans, p[i] + res[i]);
    }

    cout << ans << endl;

    return 0;
}

C++