Submission #590117

#	Time	Username	Problem	Language	Result	Execution time	Memory
590117		davi_bart	Weirdtree (RMI21_weirdtree)	C++14	100 / 100	1196 ms	52592 KiB

weirdtree

#pragma GCC optimize("O3")
#include <bits/stdc++.h>

#include "weirdtree.h"
#define ll long long
#define fi first
#define se second
#define pb push_back
#define int ll
using namespace std;
struct segtree_beats {
    struct node {
        int ma1, ma2, freq;
        int sum, abbassa;
        node(int a = -1, int b = -1, int c = 1, int d = 0, int e = -1) {
            ma1 = a;
            ma2 = b;
            freq = c;
            sum = d;
            abbassa = e;
        }
    };
    static const int dim = 1 << 19;
    vector<node> s = vector<node>(2 * dim);
    void sist(int pos, int l, int r) {
        if (s[pos].abbassa == -1) return;
        if (s[pos].ma1 <= s[pos].abbassa) {
            s[pos].abbassa = -1;
            return;
        }
        s[pos].sum -= (s[pos].ma1 - s[pos].abbassa) * s[pos].freq;
        s[pos].ma1 = s[pos].abbassa;
        if (pos < dim) {
            if (s[2 * pos].abbassa == -1 || s[2 * pos].abbassa > s[pos].abbassa) s[2 * pos].abbassa = s[pos].abbassa;
            if (s[2 * pos + 1].abbassa == -1 || s[2 * pos + 1].abbassa > s[pos].abbassa) s[2 * pos + 1].abbassa = s[pos].abbassa;
        }
        s[pos].abbassa = -1;
    }
    void recalc(int pos) {
        if (s[2 * pos].ma1 > s[2 * pos + 1].ma1) {
            s[pos].ma1 = s[2 * pos].ma1;
            s[pos].freq = s[2 * pos].freq;
            s[pos].ma2 = max(s[2 * pos].ma2, s[2 * pos + 1].ma1);
        } else if (s[2 * pos].ma1 < s[2 * pos + 1].ma1) {
            s[pos].ma1 = s[2 * pos + 1].ma1;
            s[pos].freq = s[2 * pos + 1].freq;
            s[pos].ma2 = max(s[2 * pos].ma1, s[2 * pos + 1].ma2);
        } else {
            s[pos].ma1 = s[2 * pos].ma1;
            s[pos].freq = s[2 * pos].freq + s[2 * pos + 1].freq;
            s[pos].ma2 = max(s[2 * pos].ma2, s[2 * pos + 1].ma2);
        }
        s[pos].sum = s[2 * pos].sum + s[2 * pos + 1].sum;
    }
    void setta(int pos, int l, int r, int p, int val) {
        sist(pos, l, r);
        if (p < l || r < p) return;
        if (l == r) {
            s[pos] = {val, -1, 1, val, -1};
            return;
        }
        int m = (l + r) / 2;
        setta(2 * pos, l, m, p, val);
        setta(2 * pos + 1, m + 1, r, p, val);
        recalc(pos);
    }
    void setta(int p, int val) { setta(1, 0, dim - 1, p, val); }

    int abbassa(int pos, int l, int r, int a, int b, int k, bool apply, int count) {
        sist(pos, l, r);
        if (b < l || r < a) return 0;
        if (s[pos].ma1 <= k) return 0;
        if (a <= l && r <= b && s[pos].ma2 < k) {
            int tot = (s[pos].ma1 - k) * s[pos].freq;
            if (apply) {
                s[pos].abbassa = k;
                sist(pos, l, r);
            }
            return tot;
        }
        int m = (l + r) / 2;
        int tot = abbassa(2 * pos, l, m, a, b, k, apply, count);
        count -= tot;
        if (count > 0) {
            tot += abbassa(2 * pos + 1, m + 1, r, a, b, k, apply, count);
        } else {
            sist(2 * pos + 1, m + 1, r);
        }
        recalc(pos);
        return tot;
    }
    int abbassa(int a, int b, int k, bool apply, int count) { return abbassa(1, 0, dim - 1, a, b, k, apply, count); }

    int abbassa1(int pos, int l, int r, int a, int b, int k, int count) {
        sist(pos, l, r);
        if (count == 0) return 0;
        if (b < l || r < a) return 0;
        if (s[pos].ma1 <= k) return 0;
        if (a <= l && r <= b && s[pos].ma2 < k && (s[pos].ma1 - k) * s[pos].freq <= count) {
            int tot = (s[pos].ma1 - k) * s[pos].freq;
            s[pos].abbassa = k;
            sist(pos, l, r);
            return tot;
        }
        int m = (l + r) / 2;
        int tot = abbassa1(2 * pos, l, m, a, b, k, count);
        count -= tot;
        tot += abbassa1(2 * pos + 1, m + 1, r, a, b, k, count);
        recalc(pos);
        return tot;
    }
    int abbassa1(int a, int b, int k, int count) { return abbassa1(1, 0, dim - 1, a, b, k, count); }

    int query(int pos, int l, int r, int a, int b) {
        sist(pos, l, r);
        if (b < l || r < a) return 0;
        if (a <= l && r <= b) return s[pos].sum;
        int m = (l + r) / 2;
        int tot = query(2 * pos, l, m, a, b) + query(2 * pos + 1, m + 1, r, a, b);
        // recalc(pos);
        return tot;
    }
    int query(int a, int b) { return query(1, 0, dim - 1, a, b); }

} seg;
int N;
void dbg() {
    // for (int i = 0; i < N; i++) cout << seg.query(i, i) << " ";
    // cout << endl;
}
void initialise(signed n, signed Q, signed h[]) {
    N = n;
    for (int i = 0; i < N; i++) {
        seg.setta(i, h[i + 1]);
    }
    dbg();
}
void cut(signed l, signed r, signed k) {
    l--;
    r--;
    int x = 0, y = 1e9 + 10;
    while (x < y) {
        int m = (x + y + 1) / 2;
        int q = seg.abbassa(l, r, m, 0, k);
        if (q < k)
            y = m - 1;
        else
            x = m;
    }
    k -= seg.abbassa(l, r, x + 1, 1, k);
    // cout << x << " " << k << endl;
    // dbg();
    seg.abbassa1(l, r, x, k);

    dbg();
}
void magic(signed i, signed x) {
    i--;
    seg.setta(i, x);
    dbg();
}
ll inspect(signed l, signed r) {
    l--;
    r--;
    return seg.query(l, r);
}

• 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