Submission #745009

#	Time	Username	Problem	Language	Result	Execution time	Memory
745009		siewjh	Weirdtree (RMI21_weirdtree)	C++17	100 / 100	488 ms	54808 KiB

weirdtree

#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 300005;

int nums;
ll height[MAXN];

struct vals{
    ll mx1, mx2, cnt1, sum;
};
vals st[MAXN * 4];
ll lazy[MAXN * 4];

vals join(vals a, vals b){
    vals res;
    if (a.mx1 > b.mx1){
        res.mx1 = a.mx1;
        res.mx2 = max(a.mx2, b.mx1);
        res.cnt1 = a.cnt1;
    }
    else if (a.mx1 < b.mx1){
        res.mx1 = b.mx1;
        res.mx2 = max(a.mx1, b.mx2);
        res.cnt1 = b.cnt1;
    }
    else{
        res.mx1 = a.mx1;
        res.mx2 = max(a.mx2, b.mx2);
        res.cnt1 = a.cnt1 + b.cnt1;
    }
    res.sum = a.sum + b.sum;
    return res;
}

void init(int ind, int s, int e){
    lazy[ind] = -1;
    if (s == e){
        st[ind] = {height[s], -1, 1, height[s]};
        return;
    }
    int m = (s + e) >> 1;
    init(ind << 1, s, m);
    init((ind << 1) + 1, m + 1, e);
    st[ind] = join(st[ind << 1], st[(ind << 1) + 1]);
}

int finalv(int ind){
    return (lazy[ind] == -1 ? st[ind].mx1 : lazy[ind]);
}

void propo(int ind, bool leaf){
    if (lazy[ind] == -1) return;
    if (!leaf){
        if (finalv(ind << 1) == st[ind].mx1) lazy[ind << 1] = lazy[ind];
        if (finalv((ind << 1) + 1) == st[ind].mx1) lazy[(ind << 1) + 1] = lazy[ind];
    }
    st[ind].sum -= st[ind].cnt1 * (st[ind].mx1 - lazy[ind]);
    st[ind].mx1 = lazy[ind];
    lazy[ind] = -1;
}

void updatemin(int ind, int s, int e, int l, int r, ll v){
    propo(ind, s == e);
    if (v >= st[ind].mx1) return;
    if (l == s && r == e){
        if (v > st[ind].mx2){
            lazy[ind] = v;
            return;
        }
    }
    int m = (s + e) >> 1;
    if (l <= m) updatemin(ind << 1, s, m, l, min(r, m), v);
    if (r > m) updatemin((ind << 1) + 1, m + 1, e, max(l, m + 1), r, v);
    propo(ind << 1, s == m); propo((ind << 1) + 1, m + 1 == e);
    st[ind] = join(st[ind << 1], st[(ind << 1) + 1]);
}

void updateset(int ind, int s, int e, int p, ll v){
    propo(ind, s == e);
    if (s == e){
        st[ind] = {v, -1, 1, v};
        return;
    }
    int m = (s + e) >> 1;
    if (p <= m) updateset(ind << 1, s, m, p, v);
    else updateset((ind << 1) + 1, m + 1, e, p, v);
    propo(ind << 1, s == m); propo((ind << 1) + 1, m + 1 == e);
    st[ind] = join(st[ind << 1], st[(ind << 1) + 1]);
}

vals query(int ind, int s, int e, int l, int r){
    propo(ind, s == e);
    int m = (s + e) >> 1;
    if (l == s && r == e) return st[ind];
    else if (r <= m) return query(ind << 1, s, m, l, r);
    else if (l > m) return query((ind << 1) + 1, m + 1, e, l, r);
    else return join(query(ind << 1, s, m, l, m), query((ind << 1) + 1, m + 1, e, m + 1, r));
}

int findkth(int ind, int s, int e, int l, int r, int &k, ll v){
    propo(ind, s == e);
    if (st[ind].mx1 < v) return -1;
    if (l == s && r == e){
        if (st[ind].cnt1 < k){
            k -= st[ind].cnt1;
            return -1;
        }
    }
    if (s == e) return s;
    int m = (s + e) >> 1;
    if (r <= m) return findkth(ind << 1, s, m, l, r, k, v);
    else if (l > m) return findkth((ind << 1) + 1, m + 1, e, l, r, k, v);
    else{
        int lres = findkth(ind << 1, s, m, l, m, k, v);
        if (lres != -1) return lres;
        return findkth((ind << 1) + 1, m + 1, e, m + 1, r, k, v);
    }
}

void initialise(int N, int Q, int h[]) {
    nums = N;
	for (int i = 1; i <= N; i++) height[i] = h[i];
	init(1, 1, nums);
}

void cut(int l, int r, int k) {
	while (k > 0){
        vals v = query(1, 1, nums, l, r);
        if (v.mx1 == 0) break;
        v.mx2 = max(v.mx2, 0ll);
        if (k >= v.cnt1 * (v.mx1 - v.mx2)){
            updatemin(1, 1, nums, l, r, v.mx2);
            k -= v.cnt1 * (v.mx1 - v.mx2);
        }
        else{
            int quot = k / v.cnt1, rem = k % v.cnt1;
            if (rem == 0) updatemin(1, 1, nums, l, r, v.mx1 - quot);
            else{
                int remind = findkth(1, 1, nums, l, r, rem, v.mx1);
                updatemin(1, 1, nums, l, remind, v.mx1 - quot - 1);
                updatemin(1, 1, nums, remind + 1, r, v.mx1 - quot);
            }
            k = 0;
        }
	}
}

void magic(int i, int x) {
	updateset(1, 1, nums, i, x);
}

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