Submission #1219227

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219227		nutella	Weirdtree (RMI21_weirdtree)	C++20	100 / 100	341 ms	32740 KiB

weirdtree

#include "weirdtree.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int infi = 1e9 + 7;

struct Info {
    ll sum = 0;
    int mx[2]{-infi, -infi}, cnt[2]{};
    Info() = default;
    Info(int x) {
        mx[0] = x;
        mx[1] = -1e9;
        cnt[0] = 1;
        sum = x;
    }
};

Info operator+(const Info &l, const Info &r) {
    Info res{};
    res.sum = l.sum + r.sum;
    res.mx[0] = max(l.mx[0], r.mx[0]);
    if (l.mx[0] == res.mx[0]) {
        res.cnt[0] += l.cnt[0];
        res.cnt[1] += l.cnt[1];
        res.mx[1] = l.mx[1];
    } else {
        res.cnt[1] += l.cnt[0] + l.cnt[1];
        res.mx[1] = l.mx[0];
    }
    if (r.mx[0] == res.mx[0]) {
        res.cnt[0] += r.cnt[0];
        res.cnt[1] += r.cnt[1];
        res.mx[1] = max(res.mx[1], r.mx[1]);
    } else {
        res.cnt[1] += r.cnt[0] + r.cnt[1];
        res.mx[1] = max(res.mx[1], r.mx[0]);
    }
    return res;
}

vector<Info> t;
vector<int> tag; // fill tag with 1e9+7
int sz = 1;

void tapply(int x, int tg) {
    if (t[x].mx[0] > tg) {
        t[x].sum -= t[x].cnt[0] * 1LL * (t[x].mx[0] - tg);
        t[x].mx[0] = tg; // SEE: WE DECREASE HERE!
        assert(t[x].mx[0] > t[x].mx[1]);
        tag[x] = tg;
    }
}

void tpush(int x) {
    if (tag[x] != infi) {
        for (int ch : {x * 2, x * 2 + 1}) {
            tapply(ch, tag[x]);
        }
        tag[x] = infi;
    }
}

void tpull(int x) {
    t[x] = t[x << 1] + t[x << 1 | 1];
}

void rangeSetMin(int l, int r, int m, int x = 1, int lx = 0, int rx = sz) { // a[i] min= m
    if (l >= rx || lx >= r || t[x].mx[0] <= m) {
        return;
    }
    if (l <= lx && rx <= r && t[x].mx[1] < m) {
        return tapply(x, m);
    }
    int mid = lx + rx >> 1;
    tpush(x);
    rangeSetMin(l, r, m, x << 1, lx, mid);
    rangeSetMin(l, r, m, x << 1 | 1, mid, rx);
    tpull(x);
}

int findKthMax(int l, int r, int &k, int m, int x = 1, int lx = 0, int rx = sz) { // inclusive
    if (l >= rx || lx >= r || t[x].mx[0] < m) {
        return -1;
    }
    if (l <= lx && rx <= r && t[x].cnt[0] < k) {
        k -= t[x].cnt[0];
        return -1;
    }
    if (lx + 1 == rx) {
        return lx;
    }
    tpush(x);
    int mid = lx + rx >> 1;
    int res = findKthMax(l, r, k, m, x << 1, lx, mid);
    if (res == -1){
        res = findKthMax(l, r, k, m, x << 1 | 1, mid, rx);
    }
    return res;
}

Info rangeSum(int l, int r, int x = 1, int lx = 0, int rx = sz) {
    if (l >= rx || lx >= r) {
        return {};
    }
    if (l <= lx && rx <= r) {
        return t[x];
    }
    int mid = lx + rx >> 1;
    tpush(x);
    return rangeSum(l, r, x << 1, lx, mid) + rangeSum(l, r, x << 1 | 1, mid, rx);
}

void modify(int i, int val, int x = 1, int lx = 0, int rx = sz) {
    if (lx + 1 == rx) {
        t[x] = Info(val);
        return;
    }
    int mid = lx + rx >> 1;
    tpush(x);
    if (i < mid) {
        modify(i, val, x << 1, lx, mid);
    } else {
        modify(i, val, x << 1 | 1, mid, rx);
    }
    tpull(x);
}

void initialise(int N, int Q, int h[]) {
    sz = 1 << __lg(N) + !!(N & (N - 1));
    tag.assign(sz << 1, infi);
    t.assign(sz << 1, {});
    for (int i = 0; i < N; ++i) {
        t[i + sz] = Info(h[i + 1]);
    }
    for (int i = sz - 1; i > 0; --i) {
        tpull(i);
    }
//    for (int i = 1; i < t.size(); ++i) {
//        cout << t[i].sum << " ";
//    }
//    cout << endl;
//    cerr << rangeSum(0, N).sum << endl;
}

void cut(int l, int r, int k) {
    --l;
    while (k > 0) {
        auto info = rangeSum(l, r);
        if (info.sum <= k) {
            rangeSetMin(l, r, 0);
            break;
        }
        if ((info.mx[0] - info.mx[1]) * 1LL * (info.cnt[0]) >= k) {
            int full = k / info.cnt[0];
            rangeSetMin(l, r, info.mx[0] - full);
            k -= full * info.cnt[0];
            if (k > 0) {
                int p = findKthMax(l, r, k, info.mx[0] - full);
                rangeSetMin(l, p + 1, info.mx[0] - full - 1);
            }
            break;
        }
        int d = (info.mx[0] - info.mx[1]) * 1LL * (info.cnt[0]);
        k -= d;
        rangeSetMin(l, r, info.mx[1]);
    }
	// Your code here.
}

void magic(int i, int x) {
    --i;
    modify(i, x);
	// Your code here.
}

ll inspect(int l, int r) {
    --l;
    return rangeSum(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