oj.uz

Submission #817444

# Submission time Handle Problem Language Result Execution time Memory
817444 2023-08-09T12:35:35 Z boris_mihov Weirdtree (RMI21_weirdtree) C++17
52 / 100
 2000 ms 57136 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47316 KB Output is correct
2 Correct 19 ms 47288 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47316 KB Output is correct
2 Correct 19 ms 47288 KB Output is correct
3 Correct 550 ms 49992 KB Output is correct
4 Correct 547 ms 50000 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47316 KB Output is correct
2 Correct 22 ms 47348 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47316 KB Output is correct
2 Correct 22 ms 47348 KB Output is correct
3 Execution timed out 2060 ms 55600 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1284 ms 56936 KB Output is correct
2 Correct 1324 ms 57136 KB Output is correct
3 Correct 41 ms 49680 KB Output is correct
4 Correct 513 ms 49356 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47316 KB Output is correct
2 Correct 19 ms 47288 KB Output is correct
3 Correct 550 ms 49992 KB Output is correct
4 Correct 547 ms 50000 KB Output is correct
5 Correct 28 ms 47316 KB Output is correct
6 Correct 22 ms 47348 KB Output is correct
7 Correct 41 ms 49680 KB Output is correct
8 Correct 513 ms 49356 KB Output is correct
9 Correct 550 ms 49984 KB Output is correct
10 Correct 539 ms 49976 KB Output is correct
11 Correct 552 ms 49952 KB Output is correct
12 Correct 531 ms 50032 KB Output is correct
13 Correct 557 ms 50148 KB Output is correct

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47316 KB Output is correct
2 Correct 19 ms 47288 KB Output is correct
3 Correct 550 ms 49992 KB Output is correct
4 Correct 547 ms 50000 KB Output is correct
5 Correct 28 ms 47316 KB Output is correct
6 Correct 22 ms 47348 KB Output is correct
7 Execution timed out 2060 ms 55600 KB Time limit exceeded
8 Halted 0 ms 0 KB -