oj.uz

Submission #933629

# Submission time Handle Problem Language Result Execution time Memory
933629 2024-02-26T01:55:52 Z Regulus Growing Trees (BOI11_grow) C++17
100 / 100
 404 ms 9176 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 7764 KB Output is correct
2 Correct 337 ms 8220 KB Output is correct
3 Correct 162 ms 8020 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 5 ms 2396 KB Output is correct
3 Correct 6 ms 2392 KB Output is correct
4 Correct 4 ms 2396 KB Output is correct
5 Correct 154 ms 3588 KB Output is correct
6 Correct 180 ms 3924 KB Output is correct
7 Correct 10 ms 2652 KB Output is correct
8 Correct 148 ms 3420 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 3924 KB Output is correct
2 Correct 181 ms 4180 KB Output is correct
3 Correct 3 ms 2648 KB Output is correct
4 Correct 145 ms 3668 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 4176 KB Output is correct
2 Correct 196 ms 4032 KB Output is correct
3 Correct 18 ms 2652 KB Output is correct
4 Correct 179 ms 3972 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 7292 KB Output is correct
2 Correct 400 ms 7760 KB Output is correct
3 Correct 57 ms 5576 KB Output is correct
4 Correct 129 ms 7516 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 357 ms 7520 KB Output is correct
2 Correct 398 ms 7908 KB Output is correct
3 Correct 165 ms 7764 KB Output is correct
4 Correct 54 ms 5684 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 320 ms 7472 KB Output is correct
2 Correct 281 ms 7816 KB Output is correct
3 Correct 170 ms 8276 KB Output is correct
4 Correct 53 ms 5712 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 8016 KB Output is correct
2 Correct 404 ms 7920 KB Output is correct
3 Correct 61 ms 7248 KB Output is correct
4 Correct 354 ms 7908 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 7956 KB Output is correct
2 Correct 346 ms 8016 KB Output is correct
3 Correct 371 ms 8348 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 9176 KB Output is correct