oj.uz

Submission #560496

# Submission time Handle Problem Language Result Execution time Memory
560496 2022-05-11T14:27:40 Z Seb Growing Trees (BOI11_grow) C++17
0 / 100
 96 ms 9500 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 7628 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 1892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 1984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 ms 5836 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 6668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 6936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 96 ms 8104 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 7584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 80 ms 9500 KB Output isn't correct
2 Halted 0 ms 0 KB -