Submission #622359

#	Time	Username	Problem	Language	Result	Execution time	Memory
622359		maeola	Weirdtree (RMI21_weirdtree)	C++17	52 / 100	2047 ms	56012 KiB

weirdtree

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

using ll = long long;

constexpr int L = 0x3f3f3f3f;

struct P
{
    int mx, freq, mx2;
    ll sum;
};

P operator + (const P &a, const P& b)
{
    P p;
    if (a.mx == b.mx)
    {
        p.mx = a.mx;
        p.mx2 = max(a.mx2, b.mx2);
        p.freq = a.freq + b.freq;
    }else if (a.mx > b.mx)
    {
        p.mx = a.mx;
        p.mx2 = max(a.mx2, b.mx);
        p.freq = a.freq;
    }else{
        p.mx = b.mx;
        p.mx2 = max(a.mx, b.mx2);
        p.freq = b.freq;
    }
    p.sum = a.sum + b.sum;
    return p;
}

struct Node
{
    int lc, rc;
    P p;
    int lazy;
};

Node nodes[5000000];
int new_node()
{
    static int upto = 0;
    auto &node = nodes[++upto];
    node.lazy = L;
    return upto;
}

void clean(int i)
{
    auto &node = nodes[i];
    if (not node.lc)
    {
        node.lc = new_node();
        node.rc = new_node();
    }
    if (node.lazy >= node.p.mx)
    {
        node.lazy = L;
        return;
    }
    node.p.sum -= (ll) node.p.freq * (node.p.mx - node.lazy);
    node.p.mx = node.lazy;
    nodes[node.lc].lazy = min(nodes[node.lc].lazy, node.lazy);
    nodes[node.rc].lazy = min(nodes[node.rc].lazy, node.lazy);
    node.lazy = L;
}

void upd(int i, int l, int r, int p, int x)
{
    auto &node = nodes[i];
    clean(i);
    if (p < l or p > r)
        return;
    if (l == r)
    {
        node.p.mx = x, node.p.freq = 1, node.p.mx2 = 0, node.p.sum = x;
        return;
    }
    int m = l + (r - l) / 2;
    upd(node.lc, l, m, p, x);
    upd(node.rc, m + 1, r, p, x);
    node.p = nodes[node.lc].p + nodes[node.rc].p;
}

void cap(int i, int l, int r, int ql, int qr, int x)
{
    auto &node = nodes[i];
    clean(i);
    if (qr < l or ql > r)
        return;
    if ((ql <= l and qr >= r and x > node.p.mx2) or l == r)
    {
        node.lazy = x;
        clean(i);
        return;
    } 
    int m = l + (r - l) / 2;
    cap(node.lc, l, m, ql, qr, x);
    cap(node.rc, m + 1, r, ql, qr, x);
    node.p = nodes[node.lc].p + nodes[node.rc].p;
}

P query(int i, int l, int r, int ql, int qr)
{
    auto &node = nodes[i];
    clean(i);
    if (qr < l or ql > r)
        return {0, 0, 0, 0};
    if (ql <= l and qr >= r)
        return node.p;
    int m = l + (r - l) / 2;
    return query(node.lc, l, m, ql, qr) + query(node.rc, m + 1, r, ql, qr);
}

int N;
int root = new_node();

void initialise(int N, int Q, int h[])
{
    ::N = N;
    for (int i = 1; i <= N; i++)
    {
        upd(root, 1, N, i, h[i]);
    }
}

void cut(int l, int r, int k)
{
    if (k <= 0) return;
    auto p = query(root, 1, N, l, r);
    int g = min<ll>(k, (ll) p.freq * (p.mx - p.mx2));
    if (p.mx == 0) return;
    int pi = g % p.freq;
    int pc = g / p.freq;
    if (pi == 0)
    {
        cap(root, 1, N, l, r, p.mx - pc);
    }else{
        int a = l, b = r + 1;
        while (b - a > 1)
        {
            int m = a + (b - a) / 2;
            auto f = query(root, 1, N, l, m - 1);
            if ((f.mx == p.mx ? f.freq : 0) >= pi)
            {
                b = m;
            }else{
                a = m;
            }
        }
#ifdef DEBUG
        auto d = query(root, 1, N, l, a);
        cout << "D: " << l << ' ' << a << ' ' << r << ' ' << d.freq << ' ' << d.mx << endl;
#endif
        cap(root, 1, N, l, a, p.mx - pc - 1);
        cap(root, 1, N, a + 1, r, p.mx - pc);
    }
    cut(l, r, k - g);
}

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

ll inspect(int l, int r)
{
    return query(root, 1, N, l, r).sum;
}

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