oj.uz

Submission #640429

# Submission time Handle Problem Language Result Execution time Memory
640429 2022-09-14T15:48:25 Z thienbao1602 Growing Trees (BOI11_grow) C++17
100 / 100
 126 ms 7496 KB 
#include    <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e5 + 55;

int n, query;
ll h[N], seg[N * 4], lazy[N * 4];

void down(int id)
{
    if (lazy[id] != 0)
    {
        seg[id * 2] += lazy[id];
        seg[id * 2 + 1] += lazy[id];
        lazy[id * 2 + 1] += lazy[id];
        lazy[id * 2]+= lazy[id];

        lazy[id] = 0;
    }
}

void build(int id, int l, int r)
{
    if (l == r)
    {
        seg[id] = h[l];
        return;
    }

    int m = (l + r) >> 1;
    build(id * 2, l, m);
    build(id * 2 + 1, m + 1, r);
    seg[id] = max(seg[id * 2], seg[id * 2 + 1]);
}

int bs(int id, int l, int r, ll x)
{
    if (seg[1] < x) return n + 1;
    if (l == r) return l;

    int m = (l + r) >> 1;
    down(id);
    if (seg[id * 2] < x) return bs(id * 2 + 1, m + 1, r, x);
     else return bs(id * 2, l, m, x);
}

void update(int id, int l, int r, int u, int v, int x)
{
    if (u > r || l > v) return;
    if (u <= l && r <= v)
    {
        seg[id] += x;
        lazy[id] += x;
        return;
    }

    int m = (l + r) >> 1;
    down(id);
    update(id * 2, l, m, u, v, x);
    update(id * 2 + 1, m + 1, r, u, v, x);
    seg[id] = max(seg[id * 2], seg[id * 2 + 1]);
}

ll get(int id, int l, int r, int pos)
{
    if (l == r)
    {
        return seg[id];
    }

    int m = (l + r) >> 1;
    down(id);
    if (pos <= m) return get(id * 2, l, m, pos);
     else return get(id * 2 + 1, m + 1, r, pos);
}

void solve()
{
    cin >> n >> query;
    for(int i=1; i<=n; i++)
    {
        cin >> h[i];
    }

    sort(h+1, h+1+n);
    build(1, 1, n);

    while(query--)
    {
        char c;
        int u, v;
        cin >> c >> u >> v;
        if (c == 'F')
        {
            int st = bs(1, 1, n, v);
            if (st == n + 1) continue;
            int ed = min(st + u - 1, n);
            ll val = get(1, 1, n, ed);
            int nextSt = bs(1, 1, n, val);
            update(1, 1, n, st, nextSt - 1, 1);
            int cnt = ed - nextSt + 1;
            if (cnt > 0)
            {
                int nextEd = bs(1, 1, n, val + 1);
                update(1, 1, n, nextEd - cnt, nextEd - 1, 1);
            }
        } else
        {
            int ma = bs(1, 1, n, v + 1);
            int mi = bs(1, 1, n, u);
            cout << ma - mi << "\n";
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 6432 KB Output is correct
2 Correct 96 ms 6868 KB Output is correct
3 Correct 81 ms 6708 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 36 ms 1664 KB Output is correct
6 Correct 44 ms 1868 KB Output is correct
7 Correct 4 ms 724 KB Output is correct
8 Correct 22 ms 1356 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 1868 KB Output is correct
2 Correct 43 ms 1944 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 32 ms 1576 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2084 KB Output is correct
2 Correct 46 ms 1968 KB Output is correct
3 Correct 8 ms 724 KB Output is correct
4 Correct 41 ms 2004 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 4060 KB Output is correct
2 Correct 96 ms 6396 KB Output is correct
3 Correct 13 ms 1876 KB Output is correct
4 Correct 63 ms 6276 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 6144 KB Output is correct
2 Correct 98 ms 6468 KB Output is correct
3 Correct 76 ms 6496 KB Output is correct
4 Correct 13 ms 1900 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 6236 KB Output is correct
2 Correct 66 ms 6396 KB Output is correct
3 Correct 75 ms 6676 KB Output is correct
4 Correct 13 ms 1824 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 6764 KB Output is correct
2 Correct 97 ms 6516 KB Output is correct
3 Correct 25 ms 5936 KB Output is correct
4 Correct 53 ms 6180 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 6604 KB Output is correct
2 Correct 89 ms 6704 KB Output is correct
3 Correct 126 ms 7092 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 7496 KB Output is correct