oj.uz

Submission #622778

# Submission time Handle Problem Language Result Execution time Memory
622778 2022-08-04T14:22:45 Z dooompy Weirdtree (RMI21_weirdtree) C++17
42 / 100
 575 ms 54928 KB 
#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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 73 ms 14108 KB Output is correct
4 Correct 94 ms 14060 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 3 ms 480 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 3 ms 480 KB Output is correct
3 Incorrect 575 ms 54928 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 53224 KB Output is correct
2 Incorrect 225 ms 53696 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 73 ms 14108 KB Output is correct
4 Correct 94 ms 14060 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 3 ms 480 KB Output is correct
7 Correct 73 ms 14112 KB Output is correct
8 Correct 110 ms 14024 KB Output is correct
9 Correct 74 ms 14044 KB Output is correct
10 Correct 97 ms 14200 KB Output is correct
11 Correct 74 ms 14116 KB Output is correct
12 Correct 13 ms 13868 KB Output is correct
13 Correct 95 ms 13580 KB Output is correct

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 73 ms 14108 KB Output is correct
4 Correct 94 ms 14060 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 3 ms 480 KB Output is correct
7 Incorrect 575 ms 54928 KB Output isn't correct
8 Halted 0 ms 0 KB -