oj.uz

Submission #649172

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

#pragma GCC inline_recursion ("on")
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

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

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

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

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

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

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

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

    inline friend void operator += (Number &a, const 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];

inline 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 (tree[node].max.value < searchedMax) return -1;
    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 (tree[node].max < original.max) return;
    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].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:8: warning: ignoring '#pragma GCC inline_recursion' [-Wunknown-pragmas]
    8 | #pragma GCC inline_recursion ("on")
      | 
weirdtree.cpp: In function 'int findFirstPos(int, int, int, int, int)':
weirdtree.cpp:163:16: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
  163 |     if (queryL <= l & r <= queryR)
      |         ~~~~~~~^~~~
weirdtree.cpp: In function 'void cut(int, int, int)':
weirdtree.cpp:282:18: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  282 |             Node res = query(1, n, 1, l, r);
      |                  ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28500 KB Output is correct
2 Correct 14 ms 28500 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28500 KB Output is correct
2 Correct 14 ms 28500 KB Output is correct
3 Correct 85 ms 29536 KB Output is correct
4 Correct 127 ms 29520 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 28500 KB Output is correct
2 Correct 25 ms 28544 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 28500 KB Output is correct
2 Correct 25 ms 28544 KB Output is correct
3 Correct 1216 ms 33132 KB Output is correct
4 Correct 383 ms 33204 KB Output is correct
5 Correct 1199 ms 33308 KB Output is correct
6 Correct 375 ms 33008 KB Output is correct
7 Execution timed out 2080 ms 29140 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2080 ms 29140 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28500 KB Output is correct
2 Correct 14 ms 28500 KB Output is correct
3 Correct 85 ms 29536 KB Output is correct
4 Correct 127 ms 29520 KB Output is correct
5 Correct 22 ms 28500 KB Output is correct
6 Correct 25 ms 28544 KB Output is correct
7 Execution timed out 2080 ms 29140 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28500 KB Output is correct
2 Correct 14 ms 28500 KB Output is correct
3 Correct 85 ms 29536 KB Output is correct
4 Correct 127 ms 29520 KB Output is correct
5 Correct 22 ms 28500 KB Output is correct
6 Correct 25 ms 28544 KB Output is correct
7 Correct 1216 ms 33132 KB Output is correct
8 Correct 383 ms 33204 KB Output is correct
9 Correct 1199 ms 33308 KB Output is correct
10 Correct 375 ms 33008 KB Output is correct
11 Execution timed out 2080 ms 29140 KB Time limit exceeded
12 Halted 0 ms 0 KB -