oj.uz

Submission #56156

# Submission time Handle Problem Language Result Execution time Memory
56156 2018-07-10T06:30:04 Z 노영훈(#1580) Growing Trees (BOI11_grow) C++11
0 / 100
 199 ms 3672 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=100010, inf=2e9;

int n, q;

struct node {
    int mx, lz;
} tree[4*MX];


int A[MX];

void busy(int v, int s, int e){
    int &z=tree[v].lz;
    if(s!=e){
        node &nd1=tree[v*2], &nd2=tree[v*2+1];
        nd1.lz+=z, nd2.lz+=z;
        nd1.mx+=z, nd2.mx+=z;
    }
    z=0;
}
void upt(int v, int s, int e, int l, int r, int val){
    if(e<l || r<s) return;
    node &nd=tree[v];
    if(l<=s && e<=r){
        nd.lz+=val;
        nd.mx+=val;
        return;
    }
    busy(v,s,e);
    upt(v*2,s,(s+e)/2,l,r,val);
    upt(v*2+1,(s+e)/2+1,e,l,r,val);
    nd.mx=max(tree[v*2].mx, tree[v*2+1].mx);
}
void upt(int l, int r, int val){
    if(r<l) return;
    upt(1,1,n,l,r,val);
}
int lb(int v, int s, int e, int h){
    busy(v,s,e);
    if(s==e) return s;
    if(tree[v*2].mx>=h) return lb(v*2,s,(s+e)/2,h);
    else return lb(v*2+1,(s+e)/2+1,e,h);
}
int lb(int h){
    if(tree[1].mx<h) return n+1;
    return lb(1,1,n,h);
}
int val(int v, int s, int e, int pos){
    if(pos<s || e<pos) return 0;
    busy(v,s,e);
    if(s==e) return tree[v].mx;
    return val(v*2,s,(s+e)/2,pos) + val(v*2+1,(s+e)/2+1,e,pos);
}
int val(int pos){
    return val(1,1,n,pos);
}


int main(){
    ios::sync_with_stdio(0); cin.tie(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++){
        upt(i, i, A[i]);
    }
    
    for(int i=1; i<=q; i++){
        char o; int x, y; cin>>o>>x>>y;
        // for(int i=1; i<=n; i++) cout<<val(i)<<' ';
        // cout<<'\n';
        if(o=='F'){
            int l=lb(y); // l부터 x개
            int v=val(l+x-1);

            int a=lb(v)-1;
            upt(l,a,1); x-=(a-l+1);

            int r=lb(v+1)-1;
            upt(r-x+1,r,1);
        }
        else{
            int l=lb(x), r=lb(y+1); r--;
            cout<<r-l+1<<'\n';
        }
    }
    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2808 KB Output is correct
2 Correct 5 ms 2808 KB Output is correct
3 Incorrect 5 ms 2808 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 180 ms 3672 KB Output isn't correct