Submission #1219228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219228		arbuzick	Weirdtree (RMI21_weirdtree)	C++20	100 / 100	1616 ms	36776 KiB

weirdtree

#include "weirdtree.h"

#include <bits/stdc++.h>

using namespace std;

constexpr int INF = 1e9 + 7;

constexpr int R = 1 << 19;

struct Node {
    int mx, cnt_mx;
    int mx2;
    long long sum;
    int assign_mn;

    Node() {
        mx = mx2 = -1;
        cnt_mx = 0;
        sum = 0;
        assign_mn = INF;
    }

    Node operator+(Node b) {
        Node c;
        c.mx = max(mx, b.mx);
        if (c.mx == mx) {
            c.cnt_mx += cnt_mx;
            c.mx2 = max(c.mx2, mx2);
        } else {
            c.mx2 = max(c.mx2, mx);
        }
        if (c.mx == b.mx) {
            c.cnt_mx += b.cnt_mx;
            c.mx2 = max(c.mx2, b.mx2);
        } else {
            c.mx2 = max(c.mx2, b.mx);
        }
        c.sum = sum + b.sum;
        return c;
    }
};

Node tree[R * 2];

void build() {
    for (int i = R - 1; i > 0; --i) {
        tree[i] = tree[i * 2] + tree[i * 2 + 1];
    }
}

void push(int node) {
    if (tree[node].assign_mn != INF) {
        if (tree[node * 2].mx > tree[node].assign_mn) {
            tree[node * 2].sum -= (tree[node * 2].mx - tree[node].assign_mn) * 1LL * tree[node * 2].cnt_mx;
            tree[node * 2].mx = tree[node].assign_mn;
            tree[node * 2].assign_mn = tree[node].assign_mn;
        }
        if (tree[node * 2 + 1].mx > tree[node].assign_mn) {
            tree[node * 2 + 1].sum -= (tree[node * 2 + 1].mx - tree[node].assign_mn) * 1LL * tree[node * 2 + 1].cnt_mx;
            tree[node * 2 + 1].mx = tree[node].assign_mn;
            tree[node * 2 + 1].assign_mn = tree[node].assign_mn;
        }
    }
    tree[node].assign_mn = INF;
}

void assign_mn(int ql, int qr, int val, int node = 1, int nl = 0, int nr = R) {
    if (qr <= nl || nr <= ql || tree[node].mx <= val) {
        return;
    }
    if (ql <= nl && nr <= qr && tree[node].mx2 < val) {
        tree[node].sum -= (tree[node].mx - val) * 1LL * tree[node].cnt_mx;
        tree[node].mx = val;
        tree[node].assign_mn = val;
        return;
    }
    push(node);
    int nm = (nl + nr) / 2;
    assign_mn(ql, qr, val, node * 2, nl, nm);
    assign_mn(ql, qr, val, node * 2 + 1, nm, nr);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

void assign_pos(int pos, int val, int node = 1, int nl = 0, int nr = R) {
    if (nl == nr - 1) {
        tree[node].mx = tree[node].sum = val;
        return;
    }
    push(node);
    int nm = (nl + nr) / 2;
    if (pos < nm) {
        assign_pos(pos, val, node * 2, nl, nm);
    } else {
        assign_pos(pos, val, node * 2 + 1, nm, nr);
    }
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

Node get(int ql, int qr, int node = 1, int nl = 0, int nr = R) {
    if (ql <= nl && nr <= qr) {
        return tree[node];
    }
    if (qr <= nl || nr <= ql) {
        return Node();
    }
    push(node);
    int nm = (nl + nr) / 2;
    Node res = get(ql, qr, node * 2, nl, nm) + get(ql, qr, node * 2 + 1, nm, nr);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
    return res;
}

void initialise(int n, int q, int h[]) {
    for (int i = 0; i < n; ++i) {
        tree[i + R].mx = h[i + 1];
        tree[i + R].cnt_mx = 1;
        tree[i + R].sum = h[i + 1];
    }
    build();
}

void cut(int l, int r, int k) {
    l--;
    while (k) {
        Node res = get(l, r);
        if ((res.mx - res.mx2) * 1LL * res.cnt_mx <= k && res.mx2 != -1) {
            k -= (res.mx - res.mx2) * 1LL * res.cnt_mx;
            assign_mn(l, r, res.mx2);
            continue;
        }
        if (res.mx2 == -1 && res.mx * 1LL * res.cnt_mx <= k) {
            assign_mn(l, r, 0);
            break;
        }
        if (k % res.cnt_mx == 0) {
            assign_mn(l, r, res.mx - k / res.cnt_mx);
        } else {
            int vl = k % res.cnt_mx;
            int ll = 0, rr = r - l;
            while (ll < rr - 1) {
                int m = (ll + rr) / 2;
                Node res_nw = get(l, l + m);
                if (res_nw.mx < res.mx || res_nw.cnt_mx <= vl) {
                    ll = m;
                } else {
                    rr = m;
                }
            }
            assign_mn(l, l + ll, res.mx - k / res.cnt_mx - 1);
            assign_mn(l + ll, r, res.mx - k / res.cnt_mx);
        }
        break;
    }
}

void magic(int i, int x) {
    i--;
    assign_pos(i, x);
}

long long int inspect(int l, int r) {
    l--;
    return get(l, r).sum;
}

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