Submission #560496

#	Time	Username	Problem	Language	Result	Execution time	Memory
560496		Seb	Growing Trees (BOI11_grow)	C++17	0 / 100	96 ms	9500 KiB

grow

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n;

struct Node {
    ll val,lazy;
    Node() : val(0LL), lazy(0LL) {}
};

void push(Node st[], ll nodo, ll ini, ll fin) {
    st[nodo].val += st[nodo].lazy;
    if (ini!=fin) {
        st[nodo*2].lazy += st[nodo].lazy;
        st[nodo*2+1].lazy += st[nodo].lazy;
    }
    st[nodo].lazy = 0;
    return;
}

void set_up(Node st[], ll num[], ll nodo = 1, ll ini = 0, ll fin = n-1) {
    if (ini==fin) {
        st[nodo].val = num[ini];
        return;
    }
    set_up(st,num,nodo*2,ini,(ini+fin)/2);
    set_up(st,num,nodo*2+1,(ini+fin)/2+1,fin);
    st[nodo].val = max(st[nodo*2].val,st[nodo*2+1].val);
    return;
}

ll search_num(Node st[], ll x, ll nodo = 1, ll ini = 0, ll fin = n-1) {
    push(st,nodo,ini,fin);
    if (st[nodo].val < x) return fin+1;
    if (ini==fin) return ini;
    if (st[nodo*2].val>=x) return search_num(st,x,nodo*2,ini,(ini+fin)/2);
    if (st[nodo*2+1].val>=x) return search_num(st,x,nodo*2+1,(ini+fin)/2+1,fin);
}

void update(Node st[], ll l, ll r, ll nodo = 1, ll ini = 0, ll fin = n-1) {
    push(st,nodo,ini,fin);
    if (r<ini || l>fin) return;
    if (l<=ini && fin<=r) {
        st[nodo].lazy++;
        push(st,nodo,ini,fin);
        return;
    }
    update(st,l,r,nodo*2,ini,(ini+fin)/2);
    update(st,l,r,nodo*2+1,(ini+fin)/2+1,fin);
    st[nodo].val = max(st[nodo*2].val,st[nodo*2+1].val);
    return;
}

ll pos(Node st[], ll p, ll nodo = 1, ll ini = 0, ll fin = n-1) {
    push(st,nodo,ini,fin);
    if (ini==fin) return st[nodo].val;
    if (p<=(ini+fin)/2) return pos(st,p,nodo*2,ini,(ini+fin)/2);
    else return pos(st,p,nodo*2+1,(ini+fin)/2+1,fin);
}

int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
ll q,i;
cin>>n>>q;
Node st[4*n];
ll num[n];
for (i=0;i<n;i++) cin>>num[i];
sort(num,num+n);
set_up(st,num);
while (q--) {
    char a;
    ll p,q;
    cin>>a>>p>>q;
    if (a=='F') {
        ll inicio,ultimo,cantidad,aux;
        inicio = search_num(st,q);
        if (inicio+p>=n) update(st,inicio,n-1);
        else {
            aux = pos(st,inicio+p-1);
            ultimo = search_num(st,aux+1)-1;
            cantidad = search_num(st,aux)-inicio;
            if (inicio>=inicio+cantidad-1) update(st,inicio,inicio+cantidad-1);
            update(st,ultimo-(p-cantidad)+1,ultimo);
        }
    }
    else {
        cout<<search_num(st,q+1)-search_num(st,p)<<"\n";
    }
}
return 0;
}

Compilation message (stderr)

grow.cpp: In function 'll search_num(Node*, ll, ll, ll, ll)':
grow.cpp:41:1: warning: control reaches end of non-void function [-Wreturn-type]
   41 | }
      | ^

• 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