oj.uz

Submission #640430

# Submission time Handle Problem Language Result Execution time Memory
640430 2022-09-14T15:49:15 Z thienbao1602 Growing Trees (BOI11_grow) C++17
0 / 100
 108 ms 5676 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;
            int cnt = u - (nextSt - st);
            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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 5180 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Incorrect 2 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 2964 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 5032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 5116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 108 ms 5136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 5240 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 5676 KB Output isn't correct
2 Halted 0 ms 0 KB -