Submission #1293648

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293648		Hamed_Ghaffari	Growing Trees (BOI11_grow)	C++20	100 / 100	96 ms	4248 KiB

grow

#include <bits/stdc++.h>
using namespace std;

#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)

const int MXN = 1e5+5;

int n, mn[MXN<<2], mx[MXN<<2], lz[MXN<<2];
inline void apply(int x, int id) {
    mn[id] += x;
    mx[id] += x;
    lz[id] += x;
}
inline void push(int id) {
    if(!lz[id]) return;
    apply(lz[id], lc);
    apply(lz[id], rc);
    lz[id] = 0;
}
void upd(int s, int e, int x, int l=1, int r=n+1, int id=1) {
    if(s>=r || l>=e) return;
    if(s<=l && r<=e) return apply(x, id);
    push(id);
    upd(s, e, x, l, mid, lc);
    upd(s, e, x, mid, r, rc);
    mn[id] = mn[lc];
    mx[id] = mx[rc];
}
int get(int x, int l=1, int r=n+1, int id=1) {
    if(r-l == 1) return mn[id];
    push(id);
    return x<mid ? get(x, l, mid, lc) : get(x, mid, r, rc);
}
int find(int x, int l=1, int r=n+1, int id=1) {
    if(mn[id]>x) return 0;
    if(mx[id]<=x) return r-l;
    push(id);
    return find(x, l, mid, lc) + find(x, mid, r, rc);
}

int q, a[MXN];

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> q;
    for(int i=1; i<=n; i++) cin >> a[i];
    sort(a+1, a+n+1);
    for(int i=1; i<=n; i++) upd(i, i+1, a[i]);
    while(q--) {
        char t;
        cin >> t;
        if(t=='F') {
            int c, h;
            cin >> c >> h;
            int L = find(h-1)+1, R = L+c-1;
            if(R>=n) {
                upd(L, n+1, 1);
                continue;
            }
            int val = get(R);
            int pos = find(val);
            if(pos==R) {
                upd(L, R+1, 1);
                continue;
            }
            int pos2 = max(find(val-1), L-1);
            upd(pos-c+(pos2+1-L)+1, pos+1, 1);
            upd(L, pos2+1, 1);
        }
        else {
            int l, r;
            cin >> l >> r;
            cout << find(r) - find(l-1) << '\n';
        }
    }
}

• 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