oj.uz

Submission #850321

# Submission time Handle Problem Language Result Execution time Memory
850321 2023-09-16T10:34:06 Z Essa2006 Growing Trees (BOI11_grow) C++14
100 / 100
 92 ms 3232 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
const int pr=18, s_p=1<<(pr), e_p=(1<<(pr+1))-1;
int n, m;
vector<int>A, S_sum;

void pre(){
    A.clear(), S_sum.clear();
    A.resize(n), S_sum.resize(1<<(pr+1));
}


void update(int ind, int c){
    S_sum[ind]+=c;
    while(ind/=2)
        S_sum[ind]+=c;
}

int get(int id, int u, int v, int l, int r){
    if(l>v || r<u)
        return 0;
    if(l>=u && r<=v)
        return S_sum[id];
    int md=(l+r)/2;
    return get(id*2, u, v, l, md)+get(id*2+1, u, v, md+1, r);
}

int get_pos(int id, int bef, int sum, bool fir, int l, int r){
    if((fir && bef+S_sum[id]<sum) || (!fir && bef>sum) || l>n-1+s_p)
        return -1;
    if(l==r){
        if(fir){
            if(bef+S_sum[id]>=sum)
                return l-s_p;
        }
        else{
            if(bef+S_sum[id]<=sum)
                return l-s_p;
        }
        return -1;
    }
    int md=(l+r)/2;
    if(fir){
        int res=get_pos(id*2, bef, sum, fir, l, md);
        if(res!=-1)
            return res;
        return get_pos(id*2+1, bef+S_sum[id*2], sum, fir, md+1, r);
    }
    else{
        int res=get_pos(id*2+1, bef+S_sum[id*2], sum, fir, md+1, r);
        if(res!=-1)
            return res;
        return get_pos(id*2, bef, sum, fir, l, md);
    }
    
}

int calc(int u, int v){
    if(u>v)
        return 0;
    return get(1, u+s_p, v+s_p, s_p, e_p);
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    pre();
    for(int i=0;i<n;i++){
        cin>>A[i];
    }
    sort(all(A));
    for(int i=n-1;i>0;i--){
        A[i]-=A[i-1];
        update(i+s_p, A[i]);
    }
    update(s_p, A[0]);
    while(m--){
        char type;
        int x, y;
        cin>>type>>x>>y;
        if(type=='F'){
            // change
            int l=get_pos(1, 0, y, 1, s_p, e_p);
            if(l==-1)
                continue;
            int r=min(n-1, l+x-1), need=calc(0, r);
            int r_fir=get_pos(1, 0, need, 1, s_p, e_p);
            int r_las=get_pos(1, 0, need, 0, s_p, e_p);
            A[l]++, update(l+s_p, 1);
            if(r_las+1<n)
                A[r_las+1]--, update(r_las+1+s_p, -1);

            if(r!=r_las){
                A[r_fir]--, update(r_fir+s_p, -1),
                A[r_las-(r-r_fir)]++, update(r_las-(r-r_fir)+s_p, 1);
            }
        }
        else{
            // print
            int l=get_pos(1, 0, x, 1, s_p, e_p);
            int r=get_pos(1, 0, y, 0, s_p, e_p);
            int ans=r-l+1;
            if(l==-1 || r==-1 || l>r)
                ans=0;
            cout<<ans<<endl;
        }
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 2904 KB Output is correct
2 Correct 77 ms 2856 KB Output is correct
3 Correct 55 ms 2828 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 2 ms 2396 KB Output is correct
3 Correct 3 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 46 ms 2896 KB Output is correct
6 Correct 48 ms 2652 KB Output is correct
7 Correct 5 ms 2392 KB Output is correct
8 Correct 34 ms 2652 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 3152 KB Output is correct
2 Correct 49 ms 2652 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 37 ms 2848 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 2900 KB Output is correct
2 Correct 58 ms 2648 KB Output is correct
3 Correct 7 ms 2392 KB Output is correct
4 Correct 48 ms 2712 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 2884 KB Output is correct
2 Correct 77 ms 3064 KB Output is correct
3 Correct 13 ms 2648 KB Output is correct
4 Correct 49 ms 2780 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 2880 KB Output is correct
2 Correct 70 ms 2836 KB Output is correct
3 Correct 57 ms 2652 KB Output is correct
4 Correct 13 ms 2648 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 2968 KB Output is correct
2 Correct 49 ms 2904 KB Output is correct
3 Correct 58 ms 2652 KB Output is correct
4 Correct 13 ms 2592 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 2908 KB Output is correct
2 Correct 71 ms 2936 KB Output is correct
3 Correct 22 ms 2908 KB Output is correct
4 Correct 51 ms 2908 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 3032 KB Output is correct
2 Correct 77 ms 2888 KB Output is correct
3 Correct 92 ms 2908 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 3232 KB Output is correct