Submission #1263900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263900		anteknne	Dungeon 3 (JOI21_ho_t5)	C++20	100 / 100	695 ms	156452 KiB

Main

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false

struct zdarz {
    int c;
    ll t;
    ll a;
    ll b;
    int i;
};

const int MAXN = 200 * 1000 + 17;
const int MAXQ = 200 * 1000 + 17;
const ll INF = ll(MAXN) * ll(MAXN);
const int MAXLOG = 20;
pll st[4 * MAXN];
ll A[MAXN];
ll B[MAXN];
stack<int> d;
ll dl[MAXN];
ll dr[MAXN];
int n, q;
int maks[MAXN][MAXLOG];
ll twyn[MAXQ];
ll spref[MAXN];
int jp[MAXN][MAXLOG];
ll suma[MAXN][MAXLOG];
vector<zdarz> vec;
pii minn[MAXN][MAXLOG];
ll U[MAXQ];

void aktualizuj (int p, int k, int i, int ind, pll x) {
    if (ind > k || ind < p) {
        return;
    }
    if (p == k) {
        st[i] = x;
        return;
    }
    int sr = (p + k)/ 2;
    aktualizuj(p, sr, i * 2, ind , x);
    aktualizuj(sr + 1, k, i * 2 + 1, ind, x);
    st[i].st = st[i * 2].st + st[i * 2 + 1].st;
    st[i].nd = st[i * 2].nd + st[i * 2 + 1].nd;
}

pll odczytaj (int p, int k, int i, int a, int b) {
    if (p > b || k < a) {
        return {0, 0};
    }
    if (a <= p && k <= b) {
        return st[i];
    }
    int sr = (p + k)/ 2;
    pll wyn = {0, 0};
    pll l = odczytaj(p, sr, i * 2, a, b);
    pll r = odczytaj(sr + 1, k, i * 2 + 1, a, b);
    wyn.st += l.st;
    wyn.st += r.st;
    wyn.nd += l.nd;
    wyn.nd += r.nd;
    return wyn;
}

void budujd () {
    for (int i = 1; i <= n; i ++) {
        spref[i + 1] = spref[i] + A[i];
    }
    for (int i = 1; i <= n; i ++) {
        while (!d.empty() && B[d.top()] >= B[i]) {
            d.pop();
        }
        if (d.empty()) {
            dl[i] = 0;
        } else {
            dl[i] = d.top();
        }
        d.push(i);
    }

    while (!d.empty()) {
        d.pop();
    }

    for (int i = n; i >= 1; i --) {
        while (!d.empty() && B[d.top()] > B[i]) {
            d.pop();
        }
        if (d.empty()) {
            dr[i] = n + 1;
        } else {
            dr[i] = d.top();
        }
        d.push(i);
    }
}

void budujjp () {
    for (int j = 0; j < MAXLOG; j ++) {
        jp[n + 1][j] = n + 1;
        suma[n + 1][j] = 0;
    }

    for (int i = 1; i <= n; i ++) {
        jp[i][0] = dr[i];
        //cout << i << " " << dr[i] << "\n";
        suma[i][0] = (spref[dr[i]] - spref[i]) * B[i];
    }

    for (int j = 1; j < MAXLOG; j ++) {
        for (int i = 1; i <= n + 1; i ++) {
            jp[i][j] = jp[jp[i][j - 1]][j - 1];
            suma[i][j] = suma[i][j - 1] + suma[jp[i][j - 1]][j - 1];
        }
    }
}

void aktd () {
    for (int i = 1; i <= n; i ++) {
        if (dl[i] == 0) {
            dl[i] = INF;
        } else {
            dl[i] = spref[i] - spref[dl[i]];
        }
    }

    for (int i = 1; i <= n; i ++) {
        if (dr[i] == n + 1) {
            dr[i] = INF;
        } else {
            dr[i] = spref[dr[i]] - spref[i];
        }
    }
}

void budujmaks () {
    for (int i = 1; i <= n; i ++) {
        maks[i][0] = A[i];
    }
    for (int j = 1; j < MAXLOG; j ++) {
        for (int i = 1; i <= n; i ++) {
            if (i + (1 << (j - 1)) <= n) {
                maks[i][j] = max(maks[i][j - 1], maks[i + (1 << (j - 1))][j - 1]);
            }
        }
    }
}

int fmaks (int l, int r) {
    int x = log2(r - l + 1);
    return max(maks[l][x], maks[r - (1 << x) + 1][x]);
}

bool comp (zdarz a, zdarz b) {
    if (a.t != b.t) {
        return a.t < b.t;
    }
    return a.c > b.c;
}

void budujmin () {
    for (int i = 1; i <= n; i ++) {
        minn[i][0] = {B[i], -i};
    }
    for (int j = 1; j < MAXLOG; j ++) {
        for (int i = 1; i <= n; i ++) {
            if (i + (1 << (j - 1)) <= n) {
                minn[i][j] = min(minn[i][j - 1], minn[i + (1 << (j - 1))][j - 1]);
            }
        }
    }
}

pair<ll, int> skok (ll p, ll u) {
    ll v = p;
    ll wyn = 0;
    for (int i = MAXLOG - 1; i >= 0; i --) {
        if (spref[jp[v][i]] - spref[p] <= u && jp[v][i] != n + 1) {
            wyn += suma[v][i];
            v = jp[v][i];
        }
    }
    return {wyn, v};
}

pii ffmin (int l, int r) {
    int x = log2(r - l + 1);
    return min(minn[l][x], minn[r - (1 << x) + 1][x]);
}

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

    cin >> n >> q;

    for (int i = 1; i <= n; i ++) {
        cin >> A[i];
    }

    for (int i = 1; i <= n; i ++) {
        cin >> B[i];
    }

    budujd();
    budujmaks();
    budujjp();
    aktd();
    budujmin();



    int a, b, u;
    for (int i = 0; i < q; i ++) {
        cin >> a >> b >> u;
        U[i] = u;
        if (fmaks(a, b - 1) <= u) {
            vec.pb({1, U[i], a, b, i});
        } else {
            twyn[i] = -1;
        }
    }

    //c, t, a, b, i
    for (int i = 1; i <= n; i ++) {
        if (dl[i] < dr[i]) {
            vec.pb({2, 0, B[i], 0, i});
            vec.pb({2, dl[i], 0, B[i] * dl[i], i});
            vec.pb({2, dr[i], -B[i], B[i] * ll(dl[i] + dr[i]), i});
            vec.pb({2, dl[i] + dr[i], 0, 0, i});
        } else if (dr[i] < dl[i]) {
            vec.pb({2, 0, B[i], 0, i});
            vec.pb({2, dr[i], 0, B[i] * dr[i], i});
            vec.pb({2, dl[i], -B[i], B[i] * ll(dl[i] + dr[i]), i});
            vec.pb({2, dl[i] + dr[i], 0, 0, i});
        } else {
            vec.pb({2, 0, B[i], 0, i});
            vec.pb({2, dl[i], -B[i], B[i] * ll(dl[i] + dr[i]), i});
            vec.pb({2, dl[i] + dr[i], 0, 0, i});
        }
    }

    sort(vec.begin(), vec.end(), comp);

    for (auto x : vec) {
        if (x.c == 2) {
            //cout << x.i << " " << x.t << " " << x.a << " " << x.b << "\n";
        }
    }

    for (auto x : vec) {
        //cout << "kol: " << x.t << " " << x.c << "\n";
        if (x.c == 2) {
            aktualizuj(1, n, 1, x.i, {x.a, x.b});
            //cout << "UPDATE\n";
        } else {

            ll u = U[x.i];
            u = min(u, spref[x.b] - spref[x.a]);

            pair<ll, int> xx = skok(x.a, u);

            //cout << xx.st << "\n";

            ll wyn = xx.st;
            int a = xx.nd;

            int ind = x.b;
            int p = x.a, k = ind;
            while (p <= k) {
                int sr = (p + k)/ 2;
                if (spref[x.b] - spref[sr] <= u) {
                    k = sr - 1;
                    ind = sr;
                } else {
                    p = sr + 1;
                }
            }

            //cout << "przedzial u z tylu:" << ind << " " << x.b << "\n";
            //cout << "cena jump: " << xx.st << "\n";

            pii imin = ffmin(ind, min(x.b, ll(n)));
            imin.nd *= (-1);

            ll out  = min(u, dr[imin.nd]);
            ll out2 = min(u, spref[x.b] - spref[imin.nd]);
            wyn -= B[imin.nd] * (out - out2);
            //wyn += B[a] * min({u, dr[a], spref[x.b] - spref[a]});
            wyn += B[a] * min({u, dr[a]});

            //cout << "odejmij: " << B[imin.nd] * (out - out2) << "\n";

            if (a + 1 <= imin.nd) {



                //cout <<

                //cout << wyn << "\n";
                pll funk = odczytaj(1, n, 1, a + 1, imin.nd);


                //cout << funk.st << " " << funk.nd << "funkcja" << "\n";

                ll wf = (funk.st * u + funk.nd);
                wyn += wf;
                //cout << a + 1 << " " << imin.nd << "\n";
                //cout << "ilefunkcje: " << wf << "\n";
            }

            twyn[x.i] = wyn;

            //cout << a << " " << imin.nd << "\n";

            //cout << x.i << ":\n";
            //cout << "kon szuk:" << a << "\n";
            //cout << "kon2 szuk:" << imin.nd << "\n";
        }
        //cout << "\n";
    }

    //cout << spref[5] - spref[2] << "\n";

    for (int i = 0; i < q; i ++) {
        cout << twyn[i] << "\n";
    }

    //cout << "\n";
    //cout << skok(4, 18).st << " " << skok(4, 18).nd << "\n";


    /*for (int i = 1; i <= n; i ++) {
        cout << dl[i] << " " << dr[i] << "\n";

    }*/

    return 0;
}

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