Submission #1307086

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307086		jwpassion1	Weirdtree (RMI21_weirdtree)	C++20	0 / 100	298 ms	589824 KiB

weirdtree

#include <bits/stdc++.h>
#include "weirdtree.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int N, h[300000];

struct Node {
    int max, max2, maxco, max2co;
    ll sum;
}seg[1048576];
int lazy[1048576];

void merge(Node &ret, Node &l, Node &r) {
    if (l.max > r.max) {
        ret.max = l.max;
        ret.maxco = l.maxco;
        if (l.max2 >= r.max) {
            ret.max2 = l.max2;
            ret.max2co = l.max2co;
            if (l.max2 == r.max) ret.max2co += r.maxco;
        }
        else {
            ret.max2 = r.max;
            ret.max2co = r.maxco;
        }
    }
    else if (l.max < r.max) {
        ret.max = r.max;
        ret.maxco = r.maxco;
        if (l.max >= r.max2) {
            ret.max2 = l.max;
            ret.max2co = l.maxco;
            if (l.max == r.max2) ret.max2co += r.max2co;
        }
        else {
            ret.max2 = r.max2;
            ret.max2co = r.max2co;
        }
    }
    else {
        ret.max = l.max;
        ret.maxco = l.maxco + r.maxco;
        if (l.max2 >= r.max2) {
            ret.max2 = l.max2;
            ret.max2co = l.max2co;
            if (l.max2 == r.max2) ret.max2co += r.max2co;
        }
        else {
            ret.max2 = r.max2;
            ret.max2co = r.max2co;
        }
    }
    ret.sum = l.sum + r.sum;
}

void init(int t1, int t2, int idx) {
    lazy[idx] = 0;
    if (t1 == t2) {
        seg[idx].max = seg[idx].sum = h[t1];
        seg[idx].max2 = -1;
        seg[idx].maxco = 1;
        seg[idx].max2co = 0;
        return;
    }
    int mid = (t1 + t2) >> 1;
    init(t1, mid, idx << 1);
    init(mid + 1, t2, idx << 1 | 1);
    merge(seg[idx], seg[idx << 1], seg[idx << 1 | 1]);
}

void dolazy(bool push, int idx) {
    if (push) {
        if (seg[idx << 1].max - lazy[idx << 1] == seg[idx].max) lazy[idx << 1] += lazy[idx];
        if (seg[idx << 1 | 1].max - lazy[idx << 1 | 1] == seg[idx].max) lazy[idx << 1 | 1] += lazy[idx];
    }
    seg[idx].max -= lazy[idx];
    seg[idx].sum -= (ll)lazy[idx] * seg[idx].maxco;
    lazy[idx] = 0;
}

void mupdate(int t1, int t2, int q, int val, int idx) {
    dolazy(t1 < t2, idx);
    if (q < t1 || t2 < q) return;
    if (t1 == t2) {
        seg[idx].max = seg[idx].sum = val;
        seg[idx].max2 = -1;
        seg[idx].maxco = 1;
        seg[idx].max2co = 0;
        return;
    }
    int mid = (t1 + t2) >> 1;
    mupdate(t1, mid, q, val, idx << 1);
    mupdate(mid + 1, t2, q, val, idx << 1 | 1);
    merge(seg[idx], seg[idx << 1], seg[idx << 1 | 1]);
}

Node query(int t1, int t2, int q1, int q2, int idx) {
    dolazy(t1 < t2, idx);
    if (q1 <= t1 && t2 <= q2) return seg[idx];
    int mid = (t1 + t2) >> 1;
    if (q2 <= mid) return query(t1, mid, q1, q2, idx << 1);
    if (mid + 1 <= q1) return query(mid + 1, t2, q1, q2, idx << 1 | 1);
    Node ret, l = query(t1, mid, q1, q2, idx << 1), r = query(mid + 1, t2, q1, q2, idx << 1 | 1);
    merge(ret, l, r);
    return ret;
}

void cupdate(int t1, int t2, int q1, int q2, int& lco, int val, int idx) {
    dolazy(t1 < t2, idx);
    if (q2 < t1 || t2 < q1 || !lco || seg[idx].max <= val) return;
    if (q1 <= t1 && t2 <= q2 && seg[idx].max2 < val && seg[idx].maxco <= lco) {
        lco -= seg[idx].maxco;
        lazy[idx] = seg[idx].max - val;
        dolazy(t1 < t2, idx);
        return;
    }
    if (t1 == t2) {
        lco--;
        seg[idx].max = seg[idx].sum = val;
        seg[idx].max2 = -1;
        seg[idx].maxco = 1;
        seg[idx].max2co = 0;
        return;
    }
    int mid = (t1 + t2) >> 1;
    cupdate(t1, mid, q1, q2, lco, val, idx << 1);
    cupdate(mid + 1, t2, q1, q2, lco, val, idx << 1 | 1);
    merge(seg[idx], seg[idx << 1], seg[idx << 1 | 1]);
}

void initialise(int Nin, int Q, int hin[]) {
    N = Nin;
    for (int i = 0; i < N; i++) h[i] = hin[i];
    init(0, N - 1, 1);
}
void cut(int l, int r, int k) {
    l--;
    r--;
    while (k) {
        Node qval = query(0, N - 1, l, r, 1);
        if (!qval.max) break;
        if (qval.maxco > k) {
            cupdate(0, N - 1, l, r, k, qval.max - 1, 1);
            assert(!k);
            break;
        }
        else {
            int cutlv = min(k / qval.maxco, qval.max - max(qval.max2, 0));
            if (!cutlv) break;
            k -= cutlv * qval.maxco;
            cupdate(0, N - 1, l, r, qval.maxco, qval.max - cutlv, 1);
            assert(!qval.maxco);
        }
    }
}
void magic(int i, int x) {
    mupdate(0, N - 1, --i, x, 1);
}
ll inspect(int l, int r) {
    inspect(l, r);
    return query(0, N - 1, --l, --r, 1).sum;
}





/*
int hinin[6] = {1, 2, 3, 1, 2, 3};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    initialise(6, 10, hinin);

    cut(1, 6, 3);
    cout << inspect(1, 6) << '\n';
    cut(1, 3, 3);
    cout << inspect(1, 6) << '\n';
    cut(1, 3, 1000);
    cout << inspect(1, 6) << '\n';
    //for (int i = 0; i < 6; i++) cout << query(0, 5, i, i, 1).sum << ' ';
    //cout << '\n';
    magic(1, 1000);
    cout << inspect(1, 6) << '\n';
    cut(1, 3, 999);
    cout << inspect(1, 5) << '\n';
}
*/

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