oj.uz

답안 #698160

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
698160 2023-02-12T17:22:47 Z Tigerpants Growing Trees (BOI11_grow) C++17
10 / 100
 269 ms 18880 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]);
}

// 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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 192 ms 15948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 6 ms 724 KB Output is correct
3 Correct 6 ms 584 KB Output is correct
4 Correct 4 ms 596 KB Output is correct
5 Correct 134 ms 2180 KB Output is correct
6 Incorrect 188 ms 2624 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 160 ms 2624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 174 ms 2704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 172 ms 12140 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 201 ms 13616 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 205 ms 14500 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 269 ms 16140 KB Output is correct
2 Incorrect 229 ms 14200 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 206 ms 15668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 237 ms 18880 KB Output is correct