Submission #622391

#	Time	Username	Problem	Language	Result	Execution time	Memory
622391		dooompy	Weirdtree (RMI21_weirdtree)	C++17	23 / 100	278 ms	53404 KiB

weirdtree

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

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



ll t[300005];

node combine(node a, node b) {
    if (a.max == b.max) {
        return {a.max, max(a.smax, b.smax), a.freqmax + b.freqmax, a.sum + b.sum};
    }
    if (a.max < b.max) {
        return {b.max, max(a.max, b.smax), b.freqmax, a.sum + b.sum};
    } else {
        return {a.max, max(a.smax, b.max), a.freqmax, a.sum + b.sum};
    }
}

node tree[300005 * 4];


ll cutoff[300005 * 4];


void reset(ll x) {
    cutoff[x] = 1e15;
}

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

//    // // cout << x << " " << l << " " << r << " " << cutoff[x] << " " << tree[x].max;
    if (cutoff[x] >= tree[x].max) {
        reset(x);
        return;
    }

    if (l == r) {
        tree[x] = {cutoff[x], 0, 1, cutoff[x]};
        reset(x);
        return;
    }

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

//        // cout << tree[x].freqmax << " " << tree[x].max << " " << cutoff[x] << endl;

        tree[x].sum -= (tree[x].freqmax * (tree[x].max - cutoff[x]));
        tree[x].max = cutoff[x];

//        // cout << "yes " << tree[x].sum << endl;
    }

    cutoff[2 * x] = min(cutoff[2 * x], cutoff[x]);
    cutoff[ 2 * x + 1] = min(cutoff[ 2 * x + 1], cutoff[x]);

    reset(x);
}

void build(ll x, ll l, ll r) {
    reset(x);
    if (l == r) {
        tree[x] = {t[l], 0, 1, t[l]};
//        // // cout << t[l] << endl;
//        // // cout << tree[x].max << " " << tree[x].freqmax << " " << l << endl;
//        // // cout << "sum " << l << " " << tree[x].sum << endl;
        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].sum << endl;
}

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);
}

pair<ll, ll> combpair(pair<ll, ll> a, pair<ll, ll> b) {
    if (a.first == b.first) {
        return {a.first, a.second + b.second};
    }
    if (a.first > b.first) {
        return a;
    } else return b;
}

pair<ll, ll> getMaxInfo(ll x, ll l, ll r, ll ql, ll qr) {

    pushdown(x, l, r);

    if (ql <= l && r <= qr) return {tree[x].max, tree[x].freqmax};
    if (l > qr || r < ql) return {0, 0};

    ll mid = (l + r) / 2;

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

ll getSecondMax(ll x, ll l, ll r, ll ql, ll qr) {

    pushdown(x, l, r);

    if (ql <= l && r <= qr) return tree[x].smax;
    if (l > qr || r < ql) return 0;

    ll mid = (l + r) / 2;

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

ll getSum(ll x, ll l, ll r, ll ql, ll qr) {

    pushdown(x, l, r);

    if (ql <= l && r <= qr) return tree[x].sum;
    if (l > qr || r < ql) return 0;

    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;
}


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

//     // cout << ql << " " << qr << " " << lazyval << endl;

    pushdown(x, l, r);

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

    if ((ql <= l && r <= qr && lazyval > tree[x].smax) || (l == r)) {
        cutoff[x] = lazyval;
//        // cout << "asdf " << l << " " << r << " " << lazyval << endl;
         // cout << tree[x].sum << endl;
        pushdown(x, l, r);
         // cout << tree[x].sum << endl;
        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, l, r);

    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;
    }

    int mid = (l + r) / 2;

    int 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) {
//    // // cout << "firts seen " << endl;
//    return;
    while (k >= 0) {
        auto maxinfo = getMaxInfo(1, 1, n, l, r);
        ll smax = getSecondMax(1, 1, n, l, r);

        if (maxinfo.first == 0) return;

        ll curavail = (maxinfo.first - smax) * maxinfo.second;


        if (k < curavail) {
            // need to split it somewhere
            ll lvls = k / maxinfo.second;
            ll remains = k % maxinfo.second;

             // cout << "bruh" << endl;
             // cout << lvls << " " << remains << endl;
            if (remains == 0) {
//                // cout << "asdf " << maxinfo.first - lvls << endl;
                lazy(1, 1, n, l, r, maxinfo.first - lvls);
            } else {
                k = 0;

                ll idx = walkdown(1, 1, n, l, r, remains, maxinfo.first);

                lazy(1, 1, n, l, idx, maxinfo.first - lvls - 1);

                lazy(1, 1, n, idx + 1, r, maxinfo.first - lvls);
            }

            k = 0; break;

        } else {

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

    return;

//    // // cout << "cutdown " << endl;
}

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

    if (l == r) {
        tree[x] = {xx, 0, 1, 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, l, mid);
    pushdown(2 * x + 1, mid + 1, r);
//    // cout << l << " " << r << endl;
//    // cout << tree[2 * x].max << " " << tree[2 * x + 1].max << endl;
    tree[x] = combine(tree[2 * x], tree[2 * x + 1]);
//    // cout << tree[x].max << " " << tree[x].smax << " " << l << " " << r << endl;

}

void magic(int i, int x ) {
    // // cout << "magic " << endl;
    setbruh(1, 1, n, i, x);
}

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

Compilation message (stderr)

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

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