oj.uz

Submission #698161

# Submission time Handle Problem Language Result Execution time Memory
698161 2023-02-12T17:29:07 Z Tigerpants Growing Trees (BOI11_grow) C++17
100 / 100
 323 ms 18376 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <numeric>

using namespace std;

typedef long long int ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<vll> vvll;
typedef vector<pll> vpll;
typedef map<ll, ll> mll;

#define rep(i, a, b) for (ll i = a; i < b; i++)
#define mp(a, b) make_pair(a, b)
#define all(a) a.begin(), a.end()
#define resz(a, b) a.resize(b)
#define sz(a) a.size()
#define fill_sz(a, x) fill_n(a.begin(), sz(a), x)

const ll H = 1000000001;
const pll none = mp(H, -1);

ll N, M;

vpll segtree;
vll lazy;
vpll left_right;

vll trees;

pll combine(pll a, pll b) {
    return mp(min<ll>(a.first, b.first), max<ll>(a.second, b.second));
}

void propagate(ll cur) {
    segtree[cur] = mp(segtree[cur].first + lazy[cur], segtree[cur].second + lazy[cur]);
    if (left_right[cur].first != left_right[cur].second) {
        lazy[2 * cur] += lazy[cur];
        lazy[2 * cur + 1] += lazy[cur];
    }
    lazy[cur] = 0;
}

void build(ll cur, ll l, ll r) {
    left_right[cur] = mp(l, r);
    lazy[cur] = 0;
    if (l == r) {
        segtree[cur] = mp(trees[l], trees[l]);
        return;
    }
    ll m = (l + r) / 2;
    build(2 * cur, l, m);
    build(2 * cur + 1, m + 1, r);
    segtree[cur] = combine(segtree[2 * cur], segtree[2 * cur + 1]);
}

pll query(ll cur, ll l, ll r) {
    propagate(cur);
    if ((left_right[cur].first > r) or (left_right[cur].second < l)) {
        return none;
    }
    if ((left_right[cur].first >= l) and (left_right[cur].second <= r)) {
        return segtree[cur];
    }
    return combine(query(2 * cur, l, r), query(2 * cur + 1, l, r));
}

void add_range(ll cur, ll l, ll r, ll x) {
    propagate(cur);
    if ((left_right[cur].first > r) or (left_right[cur].second < l)) {
        return;
    }
    if ((left_right[cur].first >= l) and (left_right[cur].second <= r)) {
        lazy[cur] += x;
        propagate(cur);
        return;
    }
    add_range(2 * cur, l, r, x);
    add_range(2 * cur + 1, l, r, x);
    segtree[cur] = combine(segtree[2 * cur], segtree[2 * cur + 1]);
}

ll first_of_height(ll cur, ll h) {
    propagate(cur);
    if (segtree[cur].second < h) return N;
    if (left_right[cur].first == left_right[cur].second) return left_right[cur].first;
    ll res = first_of_height(2 * cur, h);
    if (res != N) return res;
    return first_of_height(2 * cur + 1, h);
}

ll last_of_height(ll cur, ll h) {
    propagate(cur);
    if (segtree[cur].first > h) return -1;
    if (left_right[cur].first == left_right[cur].second) return left_right[cur].first;
    ll res = last_of_height(2 * cur + 1, h);
    if (res != -1) return res;
    return last_of_height(2 * cur, h);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M;
    resz(trees, N);
    resz(segtree, 4 * N);
    resz(lazy, 4 * N);
    resz(left_right, 4 * N);
    rep(i, 0, N) {
        cin >> trees[i];
    }

    sort(all(trees));
    build(1, 0, N - 1);

    rep(q, 0, M) {
        char type;
        cin >> type;
        if (type == 'F') {
            ll c, h;
            cin >> c >> h;
            ll i = first_of_height(1, h);
            if (i == N) continue;
            c = min<ll>(c, N - i);
            ll h2 = query(1, i + c - 1, i + c - 1).first;
            ll j = first_of_height(1, h2);
            ll k = last_of_height(1, h2);
            add_range(1, i, j - 1, 1);

            add_range(1, k + j + 1 - c - i, k, 1);
        } else { // (type == 'C')
            ll l, r;
            cin >> l >> r;
            l = first_of_height(1, l);
            r = last_of_height(1, r);
            cout << r - l + 1 << endl;
        }
    }

    cout << flush;
    
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 15092 KB Output is correct
2 Correct 323 ms 16196 KB Output is correct
3 Correct 318 ms 15508 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 676 KB Output is correct
2 Correct 6 ms 596 KB Output is correct
3 Correct 7 ms 620 KB Output is correct
4 Correct 5 ms 588 KB Output is correct
5 Correct 146 ms 1480 KB Output is correct
6 Correct 183 ms 1544 KB Output is correct
7 Correct 9 ms 1236 KB Output is correct
8 Correct 152 ms 1816 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 1872 KB Output is correct
2 Correct 176 ms 2784 KB Output is correct
3 Correct 3 ms 1364 KB Output is correct
4 Correct 158 ms 2372 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 1996 KB Output is correct
2 Correct 184 ms 2740 KB Output is correct
3 Correct 15 ms 1492 KB Output is correct
4 Correct 178 ms 2924 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 11268 KB Output is correct
2 Correct 255 ms 13500 KB Output is correct
3 Correct 46 ms 3556 KB Output is correct
4 Correct 245 ms 13444 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 12812 KB Output is correct
2 Correct 249 ms 14640 KB Output is correct
3 Correct 300 ms 13492 KB Output is correct
4 Correct 41 ms 3540 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 13816 KB Output is correct
2 Correct 200 ms 16088 KB Output is correct
3 Correct 313 ms 15112 KB Output is correct
4 Correct 40 ms 3628 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 14680 KB Output is correct
2 Correct 249 ms 13264 KB Output is correct
3 Correct 52 ms 17484 KB Output is correct
4 Correct 238 ms 16248 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 14768 KB Output is correct
2 Correct 227 ms 16324 KB Output is correct
3 Correct 293 ms 18376 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 17072 KB Output is correct