Submission #645015

#	Time	Username	Problem	Language	Result	Execution time	Memory
645015		danikoynov	Weirdtree (RMI21_weirdtree)	C++14	100 / 100	1842 ms	14052 KiB

weirdtree

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 300100, maxblock = sqrt(maxn) + 10, inf = 1e9 + 10;

ll n, q, h[maxn], block;
ll lazy[maxblock], sum[maxblock];
ll mx1[maxblock], fr[maxblock], mx2[maxblock];

void initialise(int N, int Q, int H[])
{
    n = N;
    q = Q;
    block = max((ll)sqrt(n), (ll)(1));
    for (int i = 1; i <= n; i ++)
    {
        h[i] = H[i];
        lazy[i / block] = inf;
        sum[i / block] += h[i];
        if (h[i] > mx1[i / block])
        {
            mx2[i / block] = mx1[i / block];
            mx1[i / block] = h[i];
            fr[i / block] = 0;
        }
        if (h[i] == mx1[i / block])
        {
            fr[i / block] ++;
        }
        else if (h[i] > mx2[i / block])
        {
            mx2[i / block] = h[i];
        }
    }
}


void update_block(int bl)
{
    mx1[bl] = mx2[bl] = 0;
    fr[bl] = 0;
    sum[bl] = 0;
    for (int i = bl * block; i < (bl + 1) * block; i ++)
    {
        h[i] = min(h[i], lazy[bl]);
        sum[bl] += h[i];
        if (h[i] > mx1[bl])
        {
            mx2[bl] = mx1[bl];
            mx1[bl] = h[i];
            fr[bl] = 0;
        }
        if (h[i] == mx1[bl])
        {
            fr[bl] ++;
        }
        else if (h[i] > mx2[bl])
        {
            mx2[bl] = h[i];
        }
    }
    lazy[bl] = inf;
}

void magic(int i, int x)
{
    update_block(i / block);
    h[i] = (ll)x;
    update_block(i / block);
}

void cut(int l, int r, int k)
{
    ///cout << l << " : " << r << " : " << k << endl;;
    while(k > 0)
    {
        ll max1 = 0, max2 = 0, freq = 0;
        ///update_block(l / block);
        ///update_block(r / block);
        for (int i = l; i < min((ll)r + 1, (l / block + 1) * block); i ++)
        {
            h[i] = min(h[i], lazy[i / block]);
            if (h[i] > max1)
            {
                max2 = max1;
                max1 = h[i];
                freq = 0;
            }
            if (h[i] == max1)
                freq ++;
            else if (h[i] > max2)
                max2 = h[i];
        }

        for (int bl = l / block + 1; bl < r / block; bl ++)
        {
            if (mx1[bl] > max1)
            {
                max2 = max1;
                max1 = mx1[bl];
                freq = 0;
            }
            if (mx1[bl] == max1)
                freq += fr[bl];
            else if (mx1[bl] > max2)
                max2 = mx1[bl];

            if (mx2[bl] > max2)
                max2 = mx2[bl];
        }

        if (l / block != r / block)
        {
            for (int i = (r / block) * block; i <= r; i ++)
            {
                h[i] = min(h[i], lazy[i / block]);
                if (h[i] > max1)
                {
                    max2 = max1;
                    max1 = h[i];
                    freq = 0;
                }
                if (h[i] == max1)
                    freq ++;
                else if (h[i] > max2)
                    max2 = h[i];
            }
        }

        if (max1 == 0)
            break;
        ///cout << "heree " << max1 << " " << max2 << " " << freq << endl;
        if (freq * (max1 - max2) <= k)
        {
            k = k - freq * (max1 - max2);
            for (int i = l; i < min((ll)r + 1, (l / block + 1) * block); i ++)
            {
                if (h[i] > max2)
                    h[i] = max2;
            }
            update_block(l / block);
            if (l / block != r / block)
            {
                for (int i = (r / block) * block; i <= r; i ++)
                {
                    if (h[i] > max2)
                        h[i] = max2;
                }
                update_block(r / block);
            }

            for (int bl = l / block + 1; bl < r / block; bl ++)
            {
                if (mx1[bl] == max1)
                {
                    lazy[bl] = max2;
                    sum[bl] -= fr[bl] * (mx1[bl] - max2);
                    mx1[bl] = max2;
                }
                if (mx1[bl] == mx2[bl])
                    update_block(bl);
            }

        }
        else
        {
            ll dec = k / freq;
            for (int i = l; i < min((ll)(r + 1), (l / block + 1) * block); i ++)
            {
                if (h[i] == max1)
                    h[i] -= dec;
            }
            update_block(l / block);

            if (l / block != r / block)
            {

                for (int i = (r / block) * block; i <= r; i ++)
                {
                    if (h[i] == max1)
                        h[i] -= dec;
                }
                update_block(r / block);
            }

            for (int bl = l / block + 1; bl < r / block; bl ++)
            {
                if (mx1[bl] == max1)
                {
                    lazy[bl] = mx1[bl] - dec;
                    sum[bl] -= fr[bl] * dec;
                    mx1[bl] -= dec;
                }
            }

            k = k - dec * freq;
            max1 -= dec;

            for (int i = l; i < min((ll)(r + 1), (l / block + 1) * block) && k > 0; i ++)
            {
                if (h[i] == max1)
                    h[i] --, k --;
            }
            update_block(l / block);

            for (int bl = l / block + 1; bl < r / block; bl ++)
            {
                if (mx1[bl] == max1)
                {
                    if (fr[bl] <= k)
                    {
                        k -= fr[bl];
                        lazy[bl] = mx1[bl] - 1;
                        sum[bl] -= fr[bl];
                        mx1[bl] --;
                        if (mx1[bl] == mx2[bl])
                            update_block(bl);
                    }
                    else
                    {
                        update_block(bl);
                        for (int i = bl * block; i < (bl + 1) * block && k > 0; i ++)
                            if (h[i] == max1)
                                h[i] --, k --;
                        update_block(bl);
                        break;
                    }
                }
            }

            if (l / block != r / block)
            {
                for (int i = (r / block) * block; i <= r && k > 0; i ++)
                {
                    if (h[i] == max1)
                        h[i] --, k --;
                }
                update_block(r / block);
            }
            break;
        }


    }
}

ll inspect(int l, int r)
{

/**for (int i = 1; i <= n; i ++)
    update_block(i / block);
    for (int i = 1; i <= n; i ++)
        cout << h[i] << " ";
    cout << endl;*/
    ///cout << l << " " << r << endl;
    ll ans = 0;
    update_block(l / block);
    for (int i = l; i < min((ll)(r + 1), (l / block + 1) * block); i ++)
    {
        ans = ans + h[i];
    }

    if (l / block != r / block)
    {
        update_block(r / block);
        for (int i = (r / block) * block; i <= r; i ++)
        {
            ans = ans + h[i];
        }
    }

    for (int bl = l / block + 1; bl < r / block; bl ++)
    {
        ans = ans + sum[bl];
    }

    return ans;
}

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