Submission #817444

#	Time	Username	Problem	Language	Result	Execution time	Memory
817444		boris_mihov	Weirdtree (RMI21_weirdtree)	C++17	52 / 100	2060 ms	57136 KiB

weirdtree

#include "weirdtree.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <set>
#include <map>

typedef long long llong;
const int MAXN = 300000 + 10;
const llong INF = 1e18;
const int INTINF = 2e9;

int n, q;
struct SegmentTree
{
    struct Node
    {
        int min;
        int max;
        int max2;
        int cntMIN;
        int cntMAX;
        llong sum;
        int lazy;

        Node()
        {
            lazy = INTINF;
        }

        void assign(int val, int len)
        {
            min = max = val;
            max2 = -INTINF;
            cntMIN = cntMAX = len;
            sum = 1LL * val * len;
        }
    };

    Node tree[4*MAXN];
    Node combine(Node left, Node right)
    {
        if (left.sum == -1)
        {
            return right;
        }

        Node res;
        res.sum = left.sum + right.sum;
        if (left.min == right.min)
        {
            res.min = left.min;
            res.cntMIN = left.cntMIN + right.cntMIN;
        } else
        {
            if (left.min > right.min)
            {
                std::swap(left, right);
            }

            res.min = left.min;
            res.cntMIN = left.cntMIN;
        }

        if (left.max == right.max)
        {
            res.max = left.max;
            res.cntMAX = left.cntMAX + right.cntMAX;
            res.max2 = std::max(left.max2, right.max2); 
        } else
        {
            if (left.max < right.max)
            {
                std::swap(left, right);
            }

            res.max = left.max;
            res.cntMAX = left.cntMAX;
            res.max2 = std::max(left.max2, right.max);
        }

        return res;
    }

    void build(int l, int r, int node, int a[])
    {
        if (l == r)
        {
            tree[node].assign(a[l], 1);
            return;
        }

        int mid = (l + r) / 2;
        build(l, mid, 2*node, a);
        build(mid + 1, r, 2*node + 1, a);
        tree[node] = combine(tree[2*node], tree[2*node + 1]);
    }

    void push(int node, int l, int r)
    {
        if (tree[node].lazy == INTINF)
        {
            return;
        }

        if (tree[node].max <= tree[node].lazy)
        {
            tree[node].lazy = INTINF;
            return;
        }
        
        if (tree[node].min >= tree[node].lazy)
        {
            tree[node].assign(tree[node].lazy, r - l + 1);
        } else if (tree[node].max2 < tree[node].lazy)
        {
            tree[node].sum -= 1LL * tree[node].cntMAX * (tree[node].max - tree[node].lazy);
            tree[node].max = tree[node].lazy;
        }

        if (l < r)
        {
            tree[2*node].lazy = std::min(tree[2*node].lazy, tree[node].lazy);
            tree[2*node + 1].lazy = std::min(tree[2*node + 1].lazy, tree[node].lazy);
        }

        tree[node].lazy = INTINF;
    }

    llong query(int l, int r, int node, int queryL, int queryR, int k)
    {
        if (queryR < l || r < queryL)
        {
            return 0;
        }

        int mid = (l + r) / 2;
        if (!(queryL <= l && r <= queryR))
        {
            return query(l, mid, 2*node, queryL, queryR, k) + query(mid + 1, r, 2*node + 1, queryL, queryR, k);
        }

        push(node, l, r);
        if (tree[node].max <= k)
        {
            return 0;
        }

        if (tree[node].min >= k)
        {
            return tree[node].sum - 1LL * (r - l + 1) * k;
        }

        if (tree[node].max2 < k)
        {
            return 1LL * tree[node].cntMAX * (tree[node].max - k); 
        }

        return query(l, mid, 2*node, queryL, queryR, k) + query(mid + 1, r, 2*node + 1, queryL, queryR, k);
    }

    void update(int l, int r, int node, int queryL, int queryR, int k)
    {
        push(node, l, r);
        if (queryR < l || r < queryL)
        {
            return;
        }

        int mid = (l + r) / 2;
        if (!(queryL <= l && r <= queryR))
        {
            update(l, mid, 2*node, queryL, queryR, k);
            update(mid + 1, r, 2*node + 1, queryL, queryR, k);
            tree[node] = combine(tree[2*node], tree[2*node + 1]);
            return;
        }

        if (tree[node].max <= k)
        {
            return;
        }

        if (tree[node].min >= k || tree[node].max2 < k)
        {
            tree[node].lazy = k;
        } else
        {
            update(l, mid, 2*node, queryL, queryR, k);
            update(mid + 1, r, 2*node + 1, queryL, queryR, k);
            tree[node] = combine(tree[2*node], tree[2*node + 1]);
            return;
        }

        push(node, l, r);
    }

    Node queryNode(int l, int r, int node, int queryL, int queryR)
    {
        // std::cout << "query Node: " << node << ' ' << l << ' ' << r << ' ' << queryL << ' ' << queryR << '\n';
        push(node, l, r);
        if(queryL <= l && r <= queryR)
        {
            return tree[node];
        }

        Node res; res.sum = -1;
        int mid = (l + r) / 2;
        if (queryL <= mid) res = combine(res, queryNode(l, mid, 2*node, queryL, queryR));
        if (mid + 1 <= queryR) res = combine(res, queryNode(mid + 1, r, 2*node + 1, queryL, queryR));
        return res;
    }

    void pointUpdate(int l, int r, int node, int queryPos, int queryVal)
    {
        push(node, l, r);
        if (queryPos < l || r < queryPos)
        {
            return;
        }

        if (l == r)
        {
            tree[node].assign(queryVal, 1);
            return;
        }

        int mid = (l + r) / 2;
        pointUpdate(l, mid, 2*node, queryPos, queryVal);
        pointUpdate(mid + 1, r, 2*node + 1, queryPos, queryVal);
        tree[node] = combine(tree[2*node], tree[2*node + 1]);
    }

    void build(int a[])
    {
        build(1, n, 1, a);
    }

    llong query(int l, int r, int k)
    {
        return query(1, n, 1, l, r, k);
    }

    void update(int l, int r, int k)
    {
        update(1, n, 1, l, r, k);
    }

    Node nodeQuery(int l, int r)
    {
        return queryNode(1, n, 1, l, r);
    }

    int cntMAX(int l, int r)
    {
        return queryNode(1, n, 1, l, r).cntMAX;
    }

    llong sumQuery(int l, int r)
    {
        return queryNode(1, n, 1, l, r).sum;
    }

    void pointUpdate(int pos, int val)
    {
        pointUpdate(1, n, 1, pos, val);
    }
};

SegmentTree tree;
void initialise(int N, int Q, int h[]) 
{
    n = N;
    q = Q;
    tree.build(h);
}

void cut(int l, int r, int k) 
{
    int valL = -1, valR = tree.nodeQuery(l, r).max + 1, mid;
    if (k >= 2)
    {
        while (valL < valR - 1)
        {
            mid = (valL + valR) / 2;
            if (tree.query(l, r, mid) > k) valL = mid;
            else valR = mid;
        }

        k -= tree.query(l, r, valR);
        tree.update(l, r, valR);
    } else
    {
        valR = tree.nodeQuery(l, r).max;
    }

    if (k > 0 && valR > 0)
    {
        int posL = l - 1, posR = r;
        while (posL < posR - 1)
        {
            mid = (posL + posR) / 2;
            SegmentTree::Node res = tree.nodeQuery(l, mid);
            if (res.max < valR || res.cntMAX < k) posL = mid;
            else posR = mid;
        }

        tree.update(l, posR, valR - 1);
    }
}

void magic(int i, int x) 
{
    tree.pointUpdate(i, x);
}

llong inspect(int l, int r) 
{
    return tree.sumQuery(l, r);
}

• 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