Submission #1187400

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187400		qrn	Growing Trees (BOI11_grow)	C++20	0 / 100	101 ms	196608 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 long long

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

struct nod {
    intt sum, mx, mn;
};

nod seg[2 * mxN];
vector<intt> lazy(2 * mxN), A(mxN);

void build(intt node, intt l, intt r) {
    if(l == r) {
        seg[node].sum = seg[node].mx = seg[node].mn = A[l];
        lazy[node] = -1;
        return;
    }

    intt mid = (l + r) / 2;
    build(node * 2, l, mid);
    build(node * 2 + 1, mid + 1, r);
    seg[node].sum = seg[node * 2].sum + seg[node * 2 + 1].sum;
    seg[node].mx = max(seg[node * 2].mx, seg[node * 2 + 1].mx);
    seg[node].mn = min(seg[node * 2].mn, seg[node * 2 + 1].mn);
}

void push(intt node, intt l, intt r){ 
    if(lazy[node] == -1) return;
    seg[node].sum += lazy[node];
    seg[node].mn += lazy[node];
    seg[node].mx += 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);
    seg[node].sum = seg[node * 2].sum + seg[node * 2 + 1].sum;
    seg[node].mx = max(seg[node * 2].mx, seg[node * 2 + 1].mx);
    seg[node].mn = min(seg[node * 2].mn, seg[node * 2 + 1].mn);
}



intt rett = -1;
intt get_cbii(intt node, intt l, intt r, intt val) {
    push(node, l, r);
    if(l == r) {
        if(seg[node].mn > val) {
            rett = l;
        } else {
            rett = -1;
        }
        return rett;
    }

    intt mid = (l + r) / 2;
    if(seg[node * 2].mx <= val && seg[node * 2 + 1].mx <= val) {
        rett = -1;
        return rett;
    }

    if(seg[node * 2].mx > val) {
        get_cbii(node * 2, l, mid, val);
    } else {
        get_cbii(node * 2 + 1, mid + 1, r, val);
    }
}

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 >> H >> C;
            intt bbii = get_cbii(1, 1, N, H-1);
            intt cbii = get_cbii(1, 1, N, H);
            if(bbii == -1) {
                rett = -1;
                continue;
            }
            if(cbii - 1 >= 1 && A[cbii - 1] == H) cbii--;
            intt equals = 0;
            if(A[bbii] == H && A[cbii] == H) {
                equals = cbii - bbii + 1;
            } else if(A[bbii] == H) {
                equals = cbii - bbii;
            }
            intt r = bbii + C - 1, boyukler = max(0ll, C - equals);
            intt r_eq = r - boyukler;
            intt l_eq = r_eq - (C - boyukler) + 1;
            update(1, 1, N, l_eq, r_eq);
            if(boyukler != 0) {
                update(1, 1, N, r_eq + 1, r_eq + boyukler);
            }
            rett = -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);
            if(bbii == -1) {
                cout << 0 << endl;
                rett = -1;
                continue;
            }       
            if(cbii == -1) {
                cbii = N+1;
            }
            cout << cbii - bbii+1 << endl;
            rett = -1;
        }
    }
}

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

*/

Compilation message (stderr)

grow.cpp: In function 'long long int get_cbii(long long int, long long int, long long int, long long int)':
grow.cpp:104:1: warning: control reaches end of non-void function [-Wreturn-type]
  104 | }
      | ^

• 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: 0 / 10