Submission #622778

#	Time	Username	Problem	Language	Result	Execution time	Memory
622778		dooompy	Weirdtree (RMI21_weirdtree)	C++17	42 / 100	575 ms	54928 KiB

weirdtree

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

struct node {
    ll max, freqmax, smax, sum;
};

ll t[300005];

node combine(node a, node b) {

    if (a.max < b.max) {
        swap(a, b);
    }

    if (a.max > b.max) {
        return {a.max, a.freqmax, max(a.smax, b.max), a.sum + b.sum};
    } else {
        return {a.max, a.freqmax + b.freqmax, max(a.smax, b.smax), a.sum + b.sum};

    }
}
    node tree[300005 * 5];

ll cutoff[300005 * 5];

bool isleaf[300005];

void pushdown(ll x) {
//    // // cout << x << " " << l << " " << r << " " << cutoff[x] << " " << tree[x].max;

    if (cutoff[x] >= tree[x].max) {
        cutoff[x] = 1e10;
        return;

    }
    if (isleaf[x]) {
        tree[x] = {cutoff[x], 1, 0, cutoff[x]};
        cutoff[x] = 1e10;
        return;
    }

    if (cutoff[x] > tree[x].smax) {

        tree[x].sum += (ll) (tree[x].freqmax * (cutoff[x] - tree[x].max));
        tree[x].max = cutoff[x];
    }
    cutoff[2 * x] = min(cutoff[2 * x], cutoff[x]);
    cutoff[ 2 * x + 1] = min(cutoff[ 2 * x + 1], cutoff[x]);

    cutoff[x] = 1e10;
}

void build(ll x, ll l, ll r) {

    cutoff[x] = 1e10;

    if (l == r) {

        tree[x] = {t[l], 1, 0, t[l]};
        isleaf[x] = true;

        return;

    }

    ll mid = (l + r) /2;

    build(2 * x, l, mid); build(2 * x + 1, mid + 1, r);

    tree[x] = combine(tree[2 * x], tree[2 * x + 1]);

//    cout << l << " " << r << " " << tree[x] << endl;

}

void printTree(int k, int l, int r){
    pushdown(k);
//    cout << l << " "  << r << " -> " << tree[k].max << " " << tree[k].freqmax << " " << tree[k].smax << endl;
    if( l == r) return;

    ll mid = (l + r) / 2;

    printTree(k << 1, l , mid);
    printTree(k << 1 | 1, mid + 1, r);
}

ll n;

void initialise(int N, int q, int h[]) {

    for (ll i = 1; i <= N; i++) {

        t[i] = h[i];

//        // // cout << t[i] << " asd " << endl;

    }

    n = N;



    // // cout << "llialise " << endl;

    build(1, 1, n);

}

node getNode(int x, int l, int r, int ql, int qr) {
    pushdown(x);

    if (ql <= l && r <= qr) return tree[x];

    ll mid =(l +r) / 2;
    if (qr <= mid) return getNode(2 * x, l, mid, ql, qr);
    else if (ql > mid) return getNode(2 * x + 1, mid + 1, r, ql, qr);

    return combine(getNode(2 * x, l, mid, ql, qr), getNode(2 * x + 1, mid + 1, r, ql, qr));
}

void lazy(ll x, ll l, ll r, ll ql, ll qr, ll lazyval) {


    pushdown(x);

    if (ql > r || qr < l || l > r || lazyval > tree[x].max) return;

    if ((ql <= l && r <= qr && lazyval > tree[x].smax) || (l == r)) {
        cutoff[x] = lazyval;
        pushdown(x);
        return;
    }

# warning may need to fix

    ll mid = (l + r) / 2;

    lazy(2 * x, l, mid, ql, qr, lazyval);
    lazy(2 * x + 1, mid + 1, r, ql, qr, lazyval);

    tree[x] = combine(tree[2 * x], tree[2 * x + 1]);

}

ll walkdown(ll x, ll l, ll r, ll ql, ll qr, ll &ct, ll maxcomp) {

    pushdown(x);
    if (tree[x].max < maxcomp || l > qr || r < ql) return 0;
    if (ql <= l && r <= qr && tree[x].freqmax < ct) {
        ct -= tree[x].freqmax;
        return 0;

    }
    if (l == r) {
        ct--;
        return l;
    }

    ll mid = (l + r) / 2;

    ll nextidx = walkdown(2 * x, l, mid, ql, qr, ct, maxcomp);
    if (nextidx) return nextidx;

    return walkdown(2 * x + 1, mid + 1, r, ql, qr, ct, maxcomp);

}

void cut(int l, int r, int k) {

    while (k > 0) {
        auto asd = getNode(1, 1, n, l, r);

        if (asd.max == 0) return;

        ll curavail = (asd.max - asd.smax) * asd.freqmax;

        if (curavail <= k) {

            lazy(1, 1, n, l, r, asd.smax);
            k -= curavail;
            continue;
        }

        ll m = k % asd.freqmax;
        ll newval = asd.max - k / asd.freqmax;

        if (m == 0) {
            lazy(1, 1, n, l, r, newval);
        } else {

            ll idx = walkdown(1, 1, n, l, r, m, asd.max);

            lazy(1, 1, n, l, idx, newval- 1);

            lazy(1, 1, n, idx + 1, r, newval);

        }

        break;

    }
    return;
}



void setbruh(ll x, ll l, ll r, ll i, ll xx) {

    pushdown(x);

    if (l == r) {

        tree[x] = {xx, 1, 0, xx};

        return;

    }

    ll mid = (l + r) / 2;



    if (i <= mid) setbruh(2 * x, l, mid, i, xx);
    else setbruh(2 * x + 1, mid + 1, r, i, xx);

    pushdown(2 * x);
    pushdown(2 * x + 1);

    tree[x] = combine(tree[2 * x], tree[2 * x + 1]);
}



void magic(int i, int x ) {

    // // cout << "magic " << endl;

    setbruh(1, 1, n, i, x);

}

ll getSum(int x, int l, int r, int ql, int qr) {
    pushdown(x);

    if (l > qr || r < ql) return 0;

    if (ql <= l && r <= qr) {
//        cout << l << " " << r << " " << ql << " " << qr << " " << tree[x].sum << endl;
        return tree[x].sum;
    }

    ll mid = (l + r) / 2;
    ll a = getSum(2 * x , l, mid, ql, qr);
    ll b = getSum(2 * x + 1, mid + 1, r, ql, qr);

    tree[x] = combine(tree[2 * x], tree[2 * x + 1]);

    return a + b;
}


ll inspect(int l, int r) {
//    printTree(1, 1, n);
    // // cout << "inspect " << endl;
    return getSum(1, 1, n, l, r);

}

Compilation message (stderr)

weirdtree.cpp:138:3: warning: #warning may need to fix [-Wcpp]
  138 | # warning may need to fix
      |   ^~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 0 / 19
• Subtask 5: 0 / 10
• Subtask 6: 21 / 21
• Subtask 7: 0 / 29