Submission #698160

#	Time	Username	Problem	Language	Result	Execution time	Memory
698160		Tigerpants	Growing Trees (BOI11_grow)	C++17	10 / 100	269 ms	18880 KiB

grow

#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]);
}

// find first index of tree with height ≥ h 
ll first_of_height(ll cur, ll h) {
    propagate(cur);
    //if (segtree[cur].second < h) return -1;
    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);
            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: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 10 / 10