Submission #541772

#	Time	Username	Problem	Language	Result	Execution time	Memory
541772		eecs	Weirdtree (RMI21_weirdtree)	C++17	100 / 100	998 ms	41076 KiB

weirdtree

#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 300010;
int n, tag[maxn << 2];
bool mark[maxn << 2];
struct node { int mx, freq, sec; ll sum; } t[maxn << 2];

node operator + (node A, node B) {
    if (A.mx < B.mx) swap(A, B);
    if (A.mx > B.mx) return {A.mx, A.freq, max(A.sec, B.mx), A.sum + B.sum};
    return {A.mx, A.freq + B.freq, max(A.sec, B.sec), A.sum + B.sum};
}

node apply(node A, int k) {
    return {min(A.mx, k), A.freq, A.sec, A.sum - 1LL * A.freq * max(0, A.mx - k)};
}

#define mid ((l + r) >> 1)
#define ls (k << 1)
#define rs (k << 1 | 1)
void apply(int k, int v) {
    if (mark[k]) {
        int x = min(v, t[k].mx);
        t[k] = {x, 1, (int)-1e9, x};
    } else if (v > t[k].sec && v < tag[k]) {
        t[k] = apply(t[k], tag[k] = v);
    } else if (v <= t[k].sec) {
        apply(ls, v), apply(rs, v);
        t[k] = t[ls] + t[rs], tag[k] = INT_MAX;
    }
}

void pushdown(int k) {
    apply(ls, tag[k]), apply(rs, tag[k]), tag[k] = INT_MAX;
}

void build(int k, int l, int r, int *h) {
    tag[k] = INT_MAX;
    if (l == r) { t[k] = {h[l], 1, (int)-1e9, h[l]}, mark[k] = 1; return; }
    build(ls, l, mid, h), build(rs, mid + 1, r, h);
    t[k] = t[ls] + t[rs];
}

void upd(int k, int l, int r, int p, int v) {
    if (l == r) { t[k] = {v, 1, (int)-1e9, v}; return; }
    pushdown(k);
    mid >= p ? upd(ls, l, mid, p, v) : upd(rs, mid + 1, r, p, v);
    t[k] = t[ls] + t[rs];
}

void modify(int k, int l, int r, int ql, int qr, int v) {
    if (l >= ql && r <= qr) return apply(k, v);
    pushdown(k);
    if (mid >= ql) modify(ls, l, mid, ql, qr, v);
    if (mid < qr) modify(rs, mid + 1, r, ql, qr, v);
    t[k] = t[ls] + t[rs];
}

int find(int k, int l, int r, int ql, int qr, int v1, int &v2) {
    if (t[k].mx < v1) return 0;
    if (l >= ql && r <= qr && t[k].freq < v2) return v2 -= t[k].freq, 0;
    if (l == r) return l;
    pushdown(k);
    int t = 0;
    if (mid >= ql) t = find(ls, l, mid, ql, qr, v1, v2);
    if (mid < qr && !t) t = find(rs, mid + 1, r, ql, qr, v1, v2);
    return t;
}

node query(int k, int l, int r, int ql, int qr) {
    if (l >= ql && r <= qr) return t[k];
    pushdown(k);
    if (mid >= qr) return query(ls, l, mid, ql, qr);
    if (mid < ql) return query(rs, mid + 1, r, ql, qr);
    return query(ls, l, mid, ql, qr) + query(rs, mid + 1, r, ql, qr);
}

void initialise(int _n, int, int *h) {
    build(1, 1, n = _n, h);
}

void cut(int l, int r, int k) {
    while (k) {
        auto p = query(1, 1, n, l, r);
        ll rem = 1LL * (p.mx - p.sec) * p.freq;
        if (rem <= k) {
            modify(1, 1, n, l, r, max(0, p.sec)), k -= rem;
        } else {
            int need = k % p.freq;
            int i = need ? find(1, 1, n, l, r, p.mx, need) : l - 1;
            if (i >= l) modify(1, 1, n, l, i, max(0, p.mx - k / p.freq - 1));
            modify(1, 1, n, i + 1, r, max(0, p.mx - k / p.freq)); break;
        }
    }
}

void magic(int i, int x) {
    upd(1, 1, n, i, x);
}

ll inspect(int l, int r) {
    return query(1, 1, n, 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