oj.uz

Submission #622359

# Submission time Handle Problem Language Result Execution time Memory
622359 2022-08-04T08:05:47 Z maeola Weirdtree (RMI21_weirdtree) C++17
52 / 100
 2000 ms 56012 KB 
#include "weirdtree.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

constexpr int L = 0x3f3f3f3f;

struct P
{
    int mx, freq, mx2;
    ll sum;
};

P operator + (const P &a, const P& b)
{
    P p;
    if (a.mx == b.mx)
    {
        p.mx = a.mx;
        p.mx2 = max(a.mx2, b.mx2);
        p.freq = a.freq + b.freq;
    }else if (a.mx > b.mx)
    {
        p.mx = a.mx;
        p.mx2 = max(a.mx2, b.mx);
        p.freq = a.freq;
    }else{
        p.mx = b.mx;
        p.mx2 = max(a.mx, b.mx2);
        p.freq = b.freq;
    }
    p.sum = a.sum + b.sum;
    return p;
}

struct Node
{
    int lc, rc;
    P p;
    int lazy;
};

Node nodes[5000000];
int new_node()
{
    static int upto = 0;
    auto &node = nodes[++upto];
    node.lazy = L;
    return upto;
}

void clean(int i)
{
    auto &node = nodes[i];
    if (not node.lc)
    {
        node.lc = new_node();
        node.rc = new_node();
    }
    if (node.lazy >= node.p.mx)
    {
        node.lazy = L;
        return;
    }
    node.p.sum -= (ll) node.p.freq * (node.p.mx - node.lazy);
    node.p.mx = node.lazy;
    nodes[node.lc].lazy = min(nodes[node.lc].lazy, node.lazy);
    nodes[node.rc].lazy = min(nodes[node.rc].lazy, node.lazy);
    node.lazy = L;
}

void upd(int i, int l, int r, int p, int x)
{
    auto &node = nodes[i];
    clean(i);
    if (p < l or p > r)
        return;
    if (l == r)
    {
        node.p.mx = x, node.p.freq = 1, node.p.mx2 = 0, node.p.sum = x;
        return;
    }
    int m = l + (r - l) / 2;
    upd(node.lc, l, m, p, x);
    upd(node.rc, m + 1, r, p, x);
    node.p = nodes[node.lc].p + nodes[node.rc].p;
}

void cap(int i, int l, int r, int ql, int qr, int x)
{
    auto &node = nodes[i];
    clean(i);
    if (qr < l or ql > r)
        return;
    if ((ql <= l and qr >= r and x > node.p.mx2) or l == r)
    {
        node.lazy = x;
        clean(i);
        return;
    } 
    int m = l + (r - l) / 2;
    cap(node.lc, l, m, ql, qr, x);
    cap(node.rc, m + 1, r, ql, qr, x);
    node.p = nodes[node.lc].p + nodes[node.rc].p;
}

P query(int i, int l, int r, int ql, int qr)
{
    auto &node = nodes[i];
    clean(i);
    if (qr < l or ql > r)
        return {0, 0, 0, 0};
    if (ql <= l and qr >= r)
        return node.p;
    int m = l + (r - l) / 2;
    return query(node.lc, l, m, ql, qr) + query(node.rc, m + 1, r, ql, qr);
}

int N;
int root = new_node();

void initialise(int N, int Q, int h[])
{
    ::N = N;
    for (int i = 1; i <= N; i++)
    {
        upd(root, 1, N, i, h[i]);
    }
}

void cut(int l, int r, int k)
{
    if (k <= 0) return;
    auto p = query(root, 1, N, l, r);
    int g = min<ll>(k, (ll) p.freq * (p.mx - p.mx2));
    if (p.mx == 0) return;
    int pi = g % p.freq;
    int pc = g / p.freq;
    if (pi == 0)
    {
        cap(root, 1, N, l, r, p.mx - pc);
    }else{
        int a = l, b = r + 1;
        while (b - a > 1)
        {
            int m = a + (b - a) / 2;
            auto f = query(root, 1, N, l, m - 1);
            if ((f.mx == p.mx ? f.freq : 0) >= pi)
            {
                b = m;
            }else{
                a = m;
            }
        }
#ifdef DEBUG
        auto d = query(root, 1, N, l, a);
        cout << "D: " << l << ' ' << a << ' ' << r << ' ' << d.freq << ' ' << d.mx << endl;
#endif
        cap(root, 1, N, l, a, p.mx - pc - 1);
        cap(root, 1, N, a + 1, r, p.mx - pc);
    }
    cut(l, r, k - g);
}

void magic(int i, int x)
{
    upd(root, 1, N, i, x);
}

ll inspect(int l, int r)
{
    return query(root, 1, N, l, r).sum;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 488 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 142 ms 14968 KB Output is correct
4 Correct 308 ms 14696 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 468 KB Output is correct
2 Correct 7 ms 484 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 468 KB Output is correct
2 Correct 7 ms 484 KB Output is correct
3 Execution timed out 2047 ms 55720 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 930 ms 53724 KB Output is correct
2 Correct 1344 ms 56012 KB Output is correct
3 Correct 45 ms 15224 KB Output is correct
4 Correct 365 ms 15004 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 488 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 142 ms 14968 KB Output is correct
4 Correct 308 ms 14696 KB Output is correct
5 Correct 6 ms 468 KB Output is correct
6 Correct 7 ms 484 KB Output is correct
7 Correct 45 ms 15224 KB Output is correct
8 Correct 365 ms 15004 KB Output is correct
9 Correct 143 ms 14976 KB Output is correct
10 Correct 327 ms 14656 KB Output is correct
11 Correct 131 ms 14476 KB Output is correct
12 Correct 332 ms 15388 KB Output is correct
13 Correct 167 ms 15596 KB Output is correct

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 488 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 142 ms 14968 KB Output is correct
4 Correct 308 ms 14696 KB Output is correct
5 Correct 6 ms 468 KB Output is correct
6 Correct 7 ms 484 KB Output is correct
7 Execution timed out 2047 ms 55720 KB Time limit exceeded
8 Halted 0 ms 0 KB -