제출 #1187455

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1187455		qrn	Growing Trees (BOI11_grow)	C++20	100 / 100	144 ms	26184 KiB

grow

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
using namespace std;
// using namespace __gnu_pbds;

#define SPEED                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(NULL);                \
    cout.tie(NULL);

#define pb push_back
#define ins insert
#define fi first
#define se second

#define endl "\n"
#define ALL(x) x.begin(), x.end()
#define sz(x) x.size()
#define intt int

const intt mod = 1e9 + 7;
const intt base = 9973;
const intt inf = 1e9;
const intt mxN = 5e5 + 5;
const intt L = 21;

vector<intt> segmax(4 * mxN), segmin(4 * mxN);
vector<intt> lazy(4 * mxN), A(mxN);

void build(intt node, intt l, intt r) {
    if(l == r) {
        segmax[node] = segmin[node] = A[l];
        lazy[node] = 0;
        return;
    }

    intt mid = (l + r) / 2;
    build(node * 2, l, mid);
    build(node * 2 + 1, mid + 1, r);
    segmax[node] = max(segmax[node * 2], segmax[node * 2 + 1]);
    segmin[node] = min(segmin[node * 2], segmin[node * 2 + 1]);
}

void push(intt node, intt l, intt r){ 
    if(lazy[node] == 0) return;
    segmax[node] += lazy[node];
    segmin[node] += lazy[node];
    if(l != r) {
        lazy[node * 2] += lazy[node];
        lazy[node * 2 + 1] += lazy[node];
    }
    lazy[node] = 0;
}

void update(intt node, intt l, intt r, intt ql, intt qr){ 
    push(node, l, r);
    if(ql > r || qr < l || ql > qr) return;

    if(ql <= l && r <= qr) {
        lazy[node]++;
        push(node, l, r);
        return;
    }

    intt mid = (l + r) / 2;
    update(node * 2, l, mid, ql, qr);
    update(node * 2 + 1, mid + 1, r, ql, qr);
    segmax[node] = max(segmax[node * 2], segmax[node * 2 + 1]);
    segmin[node] = min(segmin[node * 2], segmin[node * 2 + 1]);
}

intt get_cbii(intt node, intt l, intt r, intt val) {
    push(node, l, r);
    if(l == r) {
        if(segmax[node] > val) {
            return l;
        } else {
            return -1;
        }
    }
    intt mid = (l + r) / 2;

    push(node * 2, l, mid);
    push(node * 2 + 1, mid + 1, r);
    if(segmax[node * 2] <= val && segmax[node * 2 + 1] <= val) {
        return -1;
    }
    if(segmax[node * 2] > val) {
        return get_cbii(node * 2, l, mid, val);
    } else {
        return get_cbii(node * 2 + 1, mid + 1, r, val);
    }
}


intt get_cbeb(intt node, intt l, intt r, intt idx) {
    push(node, l, r);
    if(l == r) {
        return segmax[node];
    }
    intt mid = (l + r) / 2;
    if(idx <= mid) {
        return get_cbeb(node * 2, l, mid, idx);
    } else {
        return get_cbeb(node * 2 + 1, mid + 1, r, idx);
    }
}

void solve() {
    intt N, Q;
    cin >> N >> Q;
    A.assign(N + 1, 0ll);
    for(intt i = 1; i <= N; i++) {
        cin >> A[i];
    }
    sort(ALL(A));
    build(1, 1, N);

    while(Q--) {
        char c;
        cin >> c;
        if(c == 'F') {
            intt H, C;
            cin >> C >> H;
            intt l = get_cbii(1, 1, N, H-1);
            if(l == -1) continue;
            intt r = min(N, l + C - 1);

            intt eded = get_cbeb(1, 1, N, r);
            intt ilk = get_cbii(1, 1, N, eded-1);
            intt kicikler = (ilk - l);
            update(1, 1, N, l, ilk-1);

            intt son = get_cbii(1, 1, N, eded);
            if(son == -1) {
                son = N+1;
            }
            intt L = son - (r - l + 1 - kicikler);
            update(1, 1, N, L, son-1);
        }  else {
            intt l , r;
            cin >> l >> r;
            intt bbii = get_cbii(1, 1, N, l - 1);
            intt cbii = get_cbii(1, 1, N, r) - 1;
            // cout << "ASD:: " << bbii << " " << cbii << endl;
            if(bbii == -1) {
                cout << 0 << endl;
                continue;
            }       
            if(cbii == -2) {
                cbii = N;
            }
            cout << max(0, cbii - bbii+1) << endl;
        }
    }
    // 1 2 3 3 5

    // 2 2 3 3 3 4 4 4 
}

signed main() {
    SPEED;

    intt tst = 1;
    // cin >> tst;
    while (tst--) {
        solve();
    }
}

/*
    Bize lazimdi bir ededden ciddi boyuk olan ilk yeri tapaq, ciddi kicik olan ilk yeri tapaq
    Bize lazimdi lazy update 
    Bu ikisini necese handle ede bilsek olacaq bomba -> elebil update edende bize lazimdiki H-a beraber olan axrinci ededleri edek, qalanlari ise eyni qalacaq

    Bize lazimdi bizden boyuk nece dene *mecbur* update olunacaq ededlerin sayi -> max(0, C[i] - equals); equals =  birinci yazdigimla tapa bilerik

*/

• 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