Submission #1265645

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265645		witek_cpp	Dungeon 3 (JOI21_ho_t5)	C++20	0 / 100	405 ms	132824 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <climits>

using namespace std;
typedef long long ll;

#define st first
#define nd second
#define f(a, c, b) for (int a = c; b > a; a++)
#define pb push_back
#define all(a) a.begin(), a.end()
#define wczytaj(a, c, n) a.resize(n); f(i, c, n) cin >> a[i];
#define sz(a) int(a.size())
#define wypisz(a, c) f(i, c, sz(a)) cout << a[i] << " "; cout << "\n";

const int MAXLOG = 18;
const ll INF = 1'000'000'000'000'000LL;

vector<ll> a; //jaka odleglosc
vector<ll> b; //jaki koszt zakupu paliwa

vector<pair<ll, ll>> f_drzewo; //drzewo funkcji liniowych (slope, intercept)
vector<ll> odl_drzewo; //maksymalne drzewo po odl
vector<pair<ll, int>> b_drzewo; //minimalne po koszcie paliwala (cost, idx)

vector<ll> pref; //sumy prefiksowe do obliczania odleglosci
vector<ll> dpl; //odleglosc do najbliższego tanszego na lewo (albo INF)
vector<pair<ll, int>> dpr; //odleglosc do najbliższego tanszego na prawo i jego indeks
vector<vector<pair<ll, int>>> jp; //jump pointers: (cost_sum, next_index)

ll maks(int l, int r) {
    ll wnk = max(odl_drzewo[l], odl_drzewo[r]);
    while (r > (l + 1)) {
        if (l % 2 == 0) {
            wnk = max(wnk, odl_drzewo[l + 1]);
        }
        if (r % 2 == 1) {
            wnk = max(wnk, odl_drzewo[r - 1]);
        }
        l /= 2;
        r /= 2;
    }
    return wnk;
}

void zmien(int ind, pair<ll, ll> zmiana) {
    f_drzewo[ind] = zmiana;
    ind /= 2;
    while (ind) {
        f_drzewo[ind] = {
            f_drzewo[ind * 2].st + f_drzewo[(ind * 2) + 1].st,
            f_drzewo[ind * 2].nd + f_drzewo[(ind * 2) + 1].nd
        };
        ind /= 2;
    }
}

int minn(int l, int r) {
    pair<ll, int> wnk = min(b_drzewo[l], b_drzewo[r]);
    while (r > (l + 1)) {
        if (l % 2 == 0) {
            wnk = min(wnk, b_drzewo[l + 1]);
        }
        if (r % 2 == 1) {
            wnk = min(wnk, b_drzewo[r - 1]);
        }
        l /= 2;
        r /= 2;
    }
    return wnk.nd;
}

pair<ll, ll> zlozenie(int l, int r) {
    pair<ll, ll> wnk = {0, 0};
    if (r < l) return wnk;
    if (r == l) return f_drzewo[r];
    wnk = {f_drzewo[r].st + f_drzewo[l].st, f_drzewo[r].nd + f_drzewo[l].nd};
    while (r > (l + 1)) {
        if (l % 2 == 0) {
            wnk.st += f_drzewo[l + 1].st;
            wnk.nd += f_drzewo[l + 1].nd;
        }
        if (r % 2 == 1) {
            wnk.st += f_drzewo[r - 1].st;
            wnk.nd += f_drzewo[r - 1].nd;
        }
        r /= 2;
        l /= 2;
    }
    return wnk;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    if (!(cin >> n >> q)) return 0;
    a.resize(n);
    b.resize(n);
    f(i, 0, n) cin >> a[i];
    f(i, 0, n) cin >> b[i];

    pref.resize(n + 1);
    pref[0] = 0;
    f(i, 1, n + 1) pref[i] = pref[i - 1] + a[i - 1];

    dpl.resize(n);
    {
        stack<int> stos;
        f(i, 0, n) {
            while (sz(stos) && b[stos.top()] > b[i]) stos.pop();
            if (sz(stos)) {
                dpl[i] = pref[i] - pref[stos.top()];
            } else {
                dpl[i] = INF;
            }
            stos.push(i);
        }
    }

    dpr.resize(n);
    {
        stack<int> stos;
        for (int i = n - 1; i >= 0; i--) {
            while (sz(stos) && b[stos.top()] >= b[i]) stos.pop();
            if (sz(stos)) {
                dpr[i] = {pref[stos.top()] - pref[i], stos.top()};
            } else {
                dpr[i] = {INF, -1};
            }
            stos.push(i);
        }
    }

    int stala = 1;
    while (stala < n) stala *= 2;

    odl_drzewo.assign(2 * stala, -INF);
    f(i, 0, n) odl_drzewo[i + stala] = a[i];
    for (int j = stala - 1; j > 0; j--) {
        odl_drzewo[j] = max(odl_drzewo[j * 2], odl_drzewo[(2 * j) + 1]);
    }

    b_drzewo.assign(2 * stala, {INF, INT_MAX});
    f(i, 0, n) b_drzewo[i + stala] = {b[i], i};
    for (int j = stala - 1; j > 0; j--) {
        b_drzewo[j] = min(b_drzewo[j * 2], b_drzewo[(j * 2) + 1]);
    }

    jp.assign(MAXLOG, vector<pair<ll, int>>(n));
    f(i, 0, n) {
        if (dpr[i].st == INF) {
            jp[0][i] = {0, i};
        } else {
            jp[0][i] = {b[i] * dpr[i].st, dpr[i].nd};
        }
    }
    f(j, 1, MAXLOG) {
        f(i, 0, n) {
            jp[j][i] = { jp[j - 1][i].st + jp[j - 1][jp[j - 1][i].nd].st,
                         jp[j - 1][jp[j - 1][i].nd].nd };
        }
    }

    // inicjalizacja f_drzewo (liście)
    f_drzewo.assign(2 * stala, {0, 0});
    f(i, 0, n) {
        f_drzewo[i + stala] = {b[i], 0}; // zostawiam twoją pierwotną inicjalizację liści
    }
    for (int j = stala - 1; j > 0; j--) {
        // POPRAWKA: sumujemy też .nd (wcześniej było 0)
        f_drzewo[j] = {
            f_drzewo[j * 2].st + f_drzewo[(j * 2) + 1].st,
            f_drzewo[j * 2].nd + f_drzewo[(j * 2) + 1].nd
        };
    }

    vector<pair<ll, pair<int, pair<int, pair<ll, ll>>>>> zamiatanie; //{u, {rodzaj, {ind, {slope, intercept}}}}
    f(i, 0, n) {
        // eventy (tak jak w Twoim kodzie)
        ll mn = min(dpl[i], dpr[i].st);
        ll mx = max(dpl[i], dpr[i].st);
        zamiatanie.pb({mn, {0, {i, {0, mn * b[i]}}}});
        zamiatanie.pb({mx, {0, {i, {-b[i], (dpl[i] + dpr[i].st) * b[i]}}}});
        zamiatanie.pb({dpl[i] + dpr[i].st, {0, {i, {0, 0}}}});
    }

    vector<pair<pair<int, int>, ll>> pytania(q);
    vector<ll> odp(q);

    int ile_zrobione = 0;

    f(i, 0, q) {
        int l, r;
        ll u;
        cin >> l >> r >> u;
        l--; r--;
        pytania[i] = {{l, r}, u};
        if (maks(l + stala, r + stala - 1) > u) {
            ile_zrobione++;
            odp[i] = -1;
        } else {
            zamiatanie.pb({u, {1, {i, {-1, -1}}}});
        }
    }

    sort(all(zamiatanie));
    reverse(all(zamiatanie));

    while (ile_zrobione < q) {
        if (zamiatanie.empty()) {
            cout << "blad\n";
            return 0;
        }
        auto ev = zamiatanie.back();
        zamiatanie.pop_back();
        int rodzaj = ev.nd.st;
        int ind = ev.nd.nd.st;
        if (rodzaj == 0) {
            zmien(ind + stala, ev.nd.nd.nd);
            continue;
        }
        ll aktl_u = pytania[ind].nd;
        int l, r, mid;
        int koniec = pytania[ind].st.nd;
        r = pytania[ind].st.nd - 1;
        l = pytania[ind].st.st;
        while (r > l) {
            mid = (l + r) / 2;
            if ((pref[koniec] - pref[mid]) <= aktl_u) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        int suf_min = minn(r + stala, koniec - 1 + stala);
        int poc = pytania[ind].st.st;
        int skacze = poc;
        ll ile_doda_skaczac = 0;
        for (int j = MAXLOG - 1; j >= 0; j--) {
            int to = jp[j][skacze].nd;
            if ((pref[to] - pref[poc]) <= aktl_u && to < koniec) {
                ile_doda_skaczac += jp[j][skacze].st;
                skacze = to;
            }
        }
        pair<ll, ll> nowa_funkcja = zlozenie(skacze + stala + 1, suf_min - 1 + stala);
        ll ile_doda_punkt = 0;
        if (skacze < suf_min) {
            // POPRAWKA: ograniczamy do środka (suf_min), a nie do 'koniec'
            ll limit = pref[suf_min] - pref[skacze];
            ile_doda_punkt = min(limit, min(aktl_u, dpr[skacze].st)) * b[skacze];
        }
        ll ile_doda_srodek = aktl_u * nowa_funkcja.st + nowa_funkcja.nd;
        ll ile_doda_kon = ((pref[koniec] - pref[suf_min]) * b[suf_min]);
        if (dpl[suf_min] <= (pref[suf_min] - pref[poc])) {
            ile_doda_kon -= (b[suf_min] * max((ll)0, (aktl_u - dpl[suf_min])));
        }
        odp[ind] = ile_doda_skaczac + ile_doda_srodek + ile_doda_kon + ile_doda_punkt;
        ile_zrobione++;
    }

    for (ll ele : odp) {
        cout << ele << "\n";
    }

    return 0;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 31
• Subtask 4: 0 / 44