Submission #1262079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262079		papaulo	Growing Trees (BOI11_grow)	C++20	100 / 100	122 ms	5572 KiB

grow

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

#define MAXN 100100
int a[MAXN];

struct Node {
    int val, lazy;
    Node(int v) : val(v), lazy(0) {}
    Node() : Node(0) {}
    Node operator+(const Node &n) {
        return Node(max(this->val, n.val));
    }
};

Node seg[4*MAXN];

void build(int n, int l, int r) {
    if(l==r) seg[n]=Node(a[l-1]);
    else {
        int mid=(l+r)/2;
        build(2*n, l, mid);
        build(2*n+1, mid+1, r);
        seg[n]=seg[2*n]+seg[2*n+1];
    }
}

void lazyPropagation(int n, int l, int r) {
    seg[n].val+=seg[n].lazy;
    if(l<r) {
        seg[2*n].lazy+=seg[n].lazy;
        seg[2*n+1].lazy+=seg[n].lazy;
    }
    seg[n].lazy=0;
}

void update(int n, int l, int r, int p, int q, int v) {
    if(l>q||p>r) {
        lazyPropagation(n, l, r);
        return;
    }
    if(l>=p&&r<=q) {
        seg[n].lazy+=v;
        lazyPropagation(n, l, r);
        return;
    }
    int mid=(l+r)/2;
    lazyPropagation(n, l, r);
    update(2*n, l, mid, p, q, v);
    update(2*n+1, mid+1, r, p, q, v);
    seg[n]=seg[2*n]+seg[2*n+1];
}

int query(int n, int l, int r, int i) {
    lazyPropagation(n, l, r);
    if(l==r) return seg[n].val;
    int mid=(l+r)/2;
    if(i<=mid) return query(2*n, l, mid, i);
    return query(2*n+1, mid+1, r, i);
}

int fstidx(int n, int l, int r, int v) {
    lazyPropagation(n, l, r);
    if(seg[n].val<v) return r+1;
    if(l==r) return l;
    int mid=(l+r)/2;
    int lq=fstidx(2*n, l, mid, v);
    if(lq<=mid) return lq;
    return fstidx(2*n+1, mid+1, r, v);
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for(int i=0;i<n;i++) cin >> a[i];
    sort(a, a+n);
    build(1, 1, n);
    ostringstream out;
    while(m--) {
        char op;
        int a, b;
        cin >> op >> a >> b;
        if(op=='F') {
            int l=fstidx(1, 1, n, b);
            if(l>n) continue;
            int r=min(n, l+a-1);
            int val=query(1, 1, n, r);
            int i1=fstidx(1, 1, n, val);
            int i2=fstidx(1, 1, n, val+1);
            if(i1>l) update(1, 1, n, l, i1-1, 1);
            int cnt=r-max(i1, l)+1;
            update(1, 1, n, i2-cnt, i2-1, 1);
        } else {
            int cnt=fstidx(1, 1, n, b+1)-fstidx(1, 1, n, a);
            out << cnt << endl;
        }
    }
    cout << out.str(); 
    //for(int i=1;i<=n;i++) cout << query(1, 1, n, i) << " ";
   // cout << endl;
    return 0;
}

• 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