oj.uz

Submission #645015

# Submission time Handle Problem Language Result Execution time Memory
645015 2022-09-25T22:55:13 Z danikoynov Weirdtree (RMI21_weirdtree) C++14
100 / 100
 1842 ms 14052 KB 
#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.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 187 ms 1700 KB Output is correct
4 Correct 198 ms 1672 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1842 ms 10716 KB Output is correct
4 Correct 1595 ms 14052 KB Output is correct
5 Correct 1835 ms 13684 KB Output is correct
6 Correct 1534 ms 13444 KB Output is correct
7 Correct 590 ms 1336 KB Output is correct
8 Correct 700 ms 1332 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 590 ms 1336 KB Output is correct
2 Correct 700 ms 1332 KB Output is correct
3 Correct 1575 ms 9220 KB Output is correct
4 Correct 1614 ms 12568 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 187 ms 1700 KB Output is correct
4 Correct 198 ms 1672 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 590 ms 1336 KB Output is correct
8 Correct 700 ms 1332 KB Output is correct
9 Correct 182 ms 1612 KB Output is correct
10 Correct 202 ms 1656 KB Output is correct
11 Correct 180 ms 1644 KB Output is correct
12 Correct 208 ms 1692 KB Output is correct
13 Correct 181 ms 1712 KB Output is correct

Subtask #7
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 187 ms 1700 KB Output is correct
4 Correct 198 ms 1672 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1842 ms 10716 KB Output is correct
8 Correct 1595 ms 14052 KB Output is correct
9 Correct 1835 ms 13684 KB Output is correct
10 Correct 1534 ms 13444 KB Output is correct
11 Correct 1575 ms 9220 KB Output is correct
12 Correct 1614 ms 12568 KB Output is correct
13 Correct 182 ms 1612 KB Output is correct
14 Correct 202 ms 1656 KB Output is correct
15 Correct 180 ms 1644 KB Output is correct
16 Correct 208 ms 1692 KB Output is correct
17 Correct 181 ms 1712 KB Output is correct
18 Correct 590 ms 1336 KB Output is correct
19 Correct 700 ms 1332 KB Output is correct
20 Correct 1202 ms 12800 KB Output is correct
21 Correct 1390 ms 13392 KB Output is correct
22 Correct 1193 ms 13220 KB Output is correct
23 Correct 1371 ms 13268 KB Output is correct
24 Correct 1203 ms 12984 KB Output is correct