제출 #640429

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
640429		thienbao1602	Growing Trees (BOI11_grow)	C++17	100 / 100	126 ms	7496 KiB

grow

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10