Submission #933629

#	Time	Username	Problem	Language	Result	Execution time	Memory
933629		Regulus	Growing Trees (BOI11_grow)	C++17	100 / 100	404 ms	9176 KiB

grow

#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(false);cin.tie(0);
#define debug(x) cerr << #x << " = " << (x) << ' '
#define bug(x) cerr << (x) << ' '
#define endl cerr << '\n'
#define all(v) (v).begin(), (v).end()
#define SZ(v) (ll)(v).size()
#define lowbit(x) (x)&-(x)
#define pb emplace_back
#define F first
#define S second
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
//#define TEST
const int N = 1e5+5;
ll n, a[N], Seg[N<<2], laz[N<<2];

inline void push(int L, int R, int v)
{
    int mid((L+R) >> 1);
    Seg[v<<1] += laz[v] * (mid-L+1);
    Seg[v<<1|1] += laz[v] * (R-mid);
    laz[v<<1] += laz[v], laz[v<<1|1] += laz[v];
    laz[v] = 0;
}

inline void modify(int L, int R, int ql, int qr, int v, ll d)
{
    if (ql > qr) return;
    if (ql <= L && R <= qr)
    {
        Seg[v] += d * (R-L+1), laz[v] += d;
        return;
    }
    int mid((L+R) >> 1);
    push(L, R, v);
    if (ql <= mid) modify(L, mid, ql, qr, v<<1, d);
    if (qr > mid) modify(mid+1, R, ql, qr, v<<1|1, d);
    Seg[v] = Seg[v<<1] + Seg[v<<1|1];
}

inline ll query(int L, int R, int ql, int qr, int v)
{
    if (ql <= L && R <= qr) return Seg[v];
    ll mid((L+R) >> 1), ret = 0;
    push(L, R, v);
    if (ql <= mid) ret += query(L, mid, ql, qr, v<<1);
    if (qr > mid) ret += query(mid+1, R, ql, qr, v<<1|1);
    return ret;
}

inline int my_lower_bound(int k)
{
    int lb = 1, ub = n, mid;
    while (lb < ub)
    {
        mid = (lb + ub) >> 1;
        if (query(1, n, mid, mid, 1) >= k) ub = mid;
        else lb = mid + 1;
    }
    if (query(1, n, n, n, 1) < k) return n + 1;
    return lb;
}

int main(void)
{ IO
    int i, Q;

    cin >> n >> Q;
    for (i=1; i <= n; ++i) cin >> a[i];
    sort(a+1, a+n+1);
    for (i=1; i <= n; ++i) modify(1, n, i, i, 1, a[i]);

    do {
        char ty; cin >> ty;
        if (ty == 'F')
        {
            int c, h; cin >> c >> h;
            int it = my_lower_bound(h);
            int R = min(it + c - 1, (int)n);

            if (R < n &&
                query(1, n, R+1, R+1, 1) == query(1, n, R, R, 1))
            {
                int val = query(1, n, R, R, 1),
                    itL = my_lower_bound(val),
                    itR = my_lower_bound(val+1),
                    cnt = R - itL + 1;
                modify(1, n, it, itL-1, 1, 1);
                modify(1, n, itR-cnt, itR-1, 1, 1);
            } else {
                modify(1, n, it, R, 1, 1);
            }
        } else {
            int L, R; cin >> L >> R;
            int itL = my_lower_bound(L);
            int itR = my_lower_bound(R+1);

            cout << itR - itL << '\n';
        }
    } while (--Q);

    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