oj.uz

Submission #649165

# Submission time Handle Problem Language Result Execution time Memory
649165 2022-10-09T13:02:03 Z boris_mihov Weirdtree (RMI21_weirdtree) C++17
21 / 100
 2000 ms 51704 KB 
#include "weirdtree.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

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

int n, q;
int a[MAXN];
struct Number
{
    llong value, count;
    Number()
    {
        value = -1;
        count = 0;
    }

    Number(llong _value, llong _count)
    {
        value = _value;
        count = _count;
    }

    inline friend bool operator < (Number a, Number b)
    {
        return a.value < b.value;
    }

    inline friend bool operator == (Number a, Number b)
    {
        return a.value == b.value;
    }

    inline friend bool operator != (Number a, Number b)
    {
        return !(a == b);
    }

    inline friend bool operator > (Number a, Number b)
    {
        return a.value > b.value;
    }

    inline friend void operator += (Number &a, Number b)
    {
        if (a.value == b.value) a.count += b.count;
        if (a.value < b.value) a = b;
    }
};

struct Node
{
    Number max, max2;  
    llong sum;
    Node()
    {
        max = max2 = {-1, 0};
        sum = 0;
    }

} tree[4*MAXN];

Node combine(Node left, Node right)
{
    Node result;
    result.sum = left.sum + right.sum;
    
    result.max = left.max;
    result.max += right.max;

    if (left.max != result.max)
    {
        result.max2 = left.max;
    } else
    {
        result.max2 = left.max2;
    }

    if (right.max != result.max)
    {
        result.max2 += right.max;
    } else
    {
        result.max2 += right.max2;
    }

    return result;
}

void build(int l, int r, int node)
{
    if (l == r)
    {
        tree[node].max2 = {-1, 0};
        tree[node].max = {a[l], 1};
        tree[node].sum = a[l];
        return;
    }

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

Node query(int l, int r, int node, int queryL, int queryR)
{
    if (queryL <= l && r <= queryR)
    {
        return tree[node];
    }

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

void updatePos(int l, int r, int node, int queryPos, int queryVal)
{
    if (l == r)
    {
        tree[node].max2 = {-1, 0};
        tree[node].max = {queryVal, 1};
        tree[node].sum = queryVal;
        return;
    }

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

int toRemove;
int searchedMax;
int findFirstPos(int l, int r, int node, int queryL, int queryR)
{
    if (l == r) 
    {
        assert(queryL <= l && r <= queryR);
        if (searchedMax != tree[node].max.value) return -1;
        if (toRemove != 1)
        {
            toRemove--;
            return -1;
        }

        return l;
    }

    if (queryL <= l & r <= queryR)
    {
        if (searchedMax != tree[node].max.value || tree[node].max.count < toRemove)
        {
            if (searchedMax == tree[node].max.value) toRemove -= tree[node].max.count;
            return -1;
        }

        int mid = (l + r) / 2;
        if (tree[node].max.value == tree[2*node].max.value && toRemove <= tree[2*node].max.count) 
        {
            return findFirstPos(l, mid, 2*node, queryL, queryR);
        }

        if (searchedMax == tree[2*node].max.value) toRemove -= tree[2*node].max.count;
        return findFirstPos(mid + 1, r, 2*node + 1, queryL, queryR);
    }

    int mid = (l + r) / 2;
    if (queryL <= mid)
    {
        int res = findFirstPos(l, mid, 2*node, queryL, queryR);
        if (res != -1) return res;
    }

    return findFirstPos(mid + 1, r, 2*node + 1, queryL, queryR);
}

void updateMAXminus(int l, int r, int node, int queryL, int queryR, int value)
{
    if (tree[node].max.value < searchedMax) return;
    if (queryL <= l && r <= queryR)
    {
        tree[node].sum -= 1LL * tree[node].max.count * value;
        tree[node].max.value -= value;
        if (l < r)
        {
            int mid = (l + r) / 2;
            updateMAXminus(l, mid, 2*node, queryL, queryR, value);
            updateMAXminus(mid + 1, r, 2*node + 1, queryL, queryR, value);
            tree[node] = combine(tree[2*node], tree[2*node + 1]);
        }

        return;
    }

    int mid = (l + r) / 2;
    if (queryL <= mid) updateMAXminus(l, mid, 2*node, queryL, queryR, value);
    if (mid + 1 <= queryR) updateMAXminus(mid + 1, r, 2*node + 1, queryL, queryR, value);
    tree[node] = combine(tree[2*node], tree[2*node + 1]);
}

Node original;
void updateMAX(int l, int r, int node, int queryL, int queryR)
{
    if (queryL > l || r > queryR)
    {
        int mid = (l + r) / 2;
        if (queryL <= mid) updateMAX(l, mid, 2*node, queryL, queryR);
        if (mid + 1 <= queryR) updateMAX(mid + 1, r, 2*node + 1, queryL, queryR);
        tree[node] = combine(tree[2*node], tree[2*node + 1]);
        return;
    }

    if (tree[node].max != original.max || tree[node].max2 != original.max2)
    {
        if (tree[node].max == original.max)
        {
            tree[node].sum -= 1LL * (tree[node].max.value - original.max2.value) * tree[node].max.count;
            tree[node].max.value = original.max2.value;
            if (l != r)
            {
                int mid = (l + r) / 2;
                updateMAX(l, mid, 2*node, queryL, queryR);
                updateMAX(mid + 1, r, 2*node + 1, queryL, queryR);
                tree[node] = combine(tree[2*node], tree[2*node + 1]);
            }
        }

        return;
    }

    tree[node].sum -= 1LL * (tree[node].max.value - original.max2.value) * tree[node].max.count;
    tree[node].max.value = original.max2.value;
    if (tree[node].max2 == original.max2) tree[node].max.count += tree[node].max2.count;
    tree[node].max2 = {-1, 0};
    if (l != r)
    {
        int mid = (l + r) / 2;
        updateMAX(l, mid, 2*node, queryL, queryR);
        updateMAX(mid + 1, r, 2*node + 1, queryL, queryR);
        tree[node] = combine(tree[2*node], tree[2*node + 1]);
    }
}

void initialise(int N, int Q, int h[]) 
{
	n = N;
    q = Q;
    for (int i = 1 ; i <= n ; ++i)
    {
        a[i] = h[i];
    }

    build(1, n, 1);
}

void cut(int l, int r, int k) 
{
	while (k >= 1)
    {
        original = query(1, n, 1, l, r); 
        if (original.max.value == 0) return;
        if (original.max2.value != -1 && k >= 1LL * (original.max.value - original.max2.value) * original.max.count)
        {
            // std::cerr << "here :)\n";
            k -= 1LL * (original.max.value - original.max2.value) * original.max.count;
            updateMAX(1, n, 1, l, r);
            Node res = query(1, n, 1, l, r);
        } else
        {
            bool firstIf = false;
            if (original.max2.value == -1)
            {
                firstIf = true;
                original.max2.value = 0;
                if (k > 1LL * original.max.value * original.max.count)
                {
                    k = 1LL * original.max.value * original.max.count;
                }
            }
    
            if (firstIf || k <= 1LL * (original.max.value - original.max2.value - 1) * original.max.count)
            {
                searchedMax = original.max.value;
                updateMAXminus(1, n, 1, l, r, k / original.max.count);
                searchedMax = original.max.value - k / original.max.count;
                k %= original.max.count;
                if (k != 0)
                {
                    toRemove = k;
                    int firstPos = findFirstPos(1, n, 1, l, r);
                    updateMAXminus(1, n, 1, l, firstPos, 1);
                    k = 0;
                }
            } else
            {
                searchedMax = original.max.value;
                updateMAXminus(1, n, 1, l, r, (original.max.value - original.max2.value - 1));
                k %= original.max.count;
                if (k == 0) 
                {
                    k = original.max.count;
                }
 
                if (k != 0)
                {
                    toRemove = k;
                    searchedMax = original.max2.value + 1;
                    int firstPos = findFirstPos(1, n, 1, l, r);
                    updateMAX(1, n, 1, l, firstPos);
                }
                k = 0;
            }
        }
    }
}

void magic(int i, int x) 
{
	updatePos(1, n, 1, i, x);
}

llong inspect(int l, int r) 
{
	return query(1, n, 1, l, r).sum;
}

Compilation message

weirdtree.cpp: In function 'int findFirstPos(int, int, int, int, int)':
weirdtree.cpp:158:16: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  158 |     if (queryL <= l & r <= queryR)
      |         ~~~~~~~^~~~
weirdtree.cpp: In function 'void cut(int, int, int)':
weirdtree.cpp:276:18: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  276 |             Node res = query(1, n, 1, l, r);
      |                  ^~~

Subtask #1
5.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47316 KB Output is correct
2 Correct 29 ms 47260 KB Output is correct
3 Correct 155 ms 48344 KB Output is correct
4 Correct 230 ms 48308 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 47264 KB Output is correct
2 Correct 49 ms 47308 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 47264 KB Output is correct
2 Correct 49 ms 47308 KB Output is correct
3 Execution timed out 2090 ms 51704 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 51148 KB Output is correct
2 Execution timed out 2073 ms 50864 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47316 KB Output is correct
2 Correct 29 ms 47260 KB Output is correct
3 Correct 155 ms 48344 KB Output is correct
4 Correct 230 ms 48308 KB Output is correct
5 Correct 41 ms 47264 KB Output is correct
6 Correct 49 ms 47308 KB Output is correct
7 Correct 164 ms 50236 KB Output is correct
8 Correct 243 ms 50244 KB Output is correct
9 Correct 159 ms 50264 KB Output is correct
10 Correct 241 ms 50292 KB Output is correct
11 Correct 153 ms 50412 KB Output is correct
12 Execution timed out 2097 ms 47944 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 47316 KB Output is correct
2 Correct 29 ms 47260 KB Output is correct
3 Correct 155 ms 48344 KB Output is correct
4 Correct 230 ms 48308 KB Output is correct
5 Correct 41 ms 47264 KB Output is correct
6 Correct 49 ms 47308 KB Output is correct
7 Execution timed out 2090 ms 51704 KB Time limit exceeded
8 Halted 0 ms 0 KB -