oj.uz

Submission #880973

# Submission time Handle Problem Language Result Execution time Memory
880973 2023-11-30T09:44:22 Z nghiaaa Growing Trees (BOI11_grow) C++14
100 / 100
 103 ms 9248 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define ii pair<int,int>
#define f first
#define s second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define all(v) v.begin(),v.end()
#define BIT(i) ((ll)1<<(i))
#define endl "\n"
#define debug(x) for (auto p: x) cout<<p<<' ';cout<<endl
#define forw(i,j,z) for(int i=(int)j;i<=(int)z;i++)
#define forw2(i,j,z,k) for(int i=(int)j;i<=(int)z;i+=k)
#define ford(i,j,z) for (int i=(int)j;i>=(int)z;i--)
#define ford2(i,j,z,k) for (int i=(int)j;i>=(int)z;i-=k)
#define sz(a) (int)a.size()
const ll inf=(ll)1<<60;
struct IT{
    int lazy;
    ll MAX;
};
const int N=100000;
ll a[N+1];
int n,q;
IT tree[4*N+1];
void build(int node,int l,int r)
{
    if (l==r)
        tree[node].MAX=a[l];
    else{
        int mid=(l+r)>>1;
        build(node<<1,l,mid);
        build(node<<1|1,mid+1,r);
        tree[node].MAX=max(tree[node<<1].MAX,tree[node<<1|1].MAX);
    }
}
void lift(int node,int val)
{
    tree[node].MAX+=val;
    tree[node].lazy+=val;
}
void pull(int node)
{
    if (tree[node].lazy)
    {
        lift(node<<1,tree[node].lazy);
        lift(node<<1|1,tree[node].lazy);
        tree[node].lazy=0;
    }
}
int find_Lower(int node,int l,int r,ll val)
{
    if (l==r)
    {
        if (tree[node].MAX>=val) return l;
        return l+1;
    }
    else{
        pull(node);
        int mid=(l+r)>>1;
        if (tree[node<<1].MAX>=val)
            return find_Lower(node<<1,l,mid,val);
        else return find_Lower(node<<1|1,mid+1,r,val);
    }
}
int getValue(int node,int l,int r,int i)
{
    if (l==r)
        return tree[node].MAX;
    else{
        pull(node);
        int mid=(l+r)>>1;
        if (i<=mid) return getValue(node<<1,l,mid,i);
        else return getValue(node<<1|1,mid+1,r,i);
    }
}
void update(int node,int l,int r,int L,int R)
{
    if (l>=L&&r<=R) lift(node,1);
    else{
        pull(node);
        int mid=(l+r)>>1;
        if (!(l>R||mid<L)) update(node<<1,l,mid,L,R);
        if (!(mid+1>R||r<L)) update(node<<1|1,mid+1,r,L,R);
        tree[node].MAX=max(tree[node<<1].MAX,tree[node<<1|1].MAX);
    }
}
void solve()
{
    cin>>n>>q;
    forw(i,1,n) cin>>a[i];
    sort(a+1,a+n+1);
    build(1,1,n);
    while(q--)
    {
        char ask;cin>>ask;
        if (ask=='C')
        {
            ll l,r;
            cin>>l>>r;
            cout<<find_Lower(1,1,n,r+1)-find_Lower(1,1,n,l)<<'\n';
        }
        else{
            int c;ll h;
            cin>>c>>h;
            int l=find_Lower(1,1,n,h),r=l+c-1;
            if (r>=n)
                update(1,1,n,l,n);
            else{
                int val=getValue(1,1,n,r);
                int L=find_Lower(1,1,n,val),R=find_Lower(1,1,n,val+1)-1;
                if (l<L) update(1,1,n,l,L-1);
                int left=c-(L-l);
                if (R-left+1<=R)
                    update(1,1,n,R-left+1,R);
            }
        }
    }
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //cout<<setprecision(6)<<fixed;
    //time_t TIME_TU=clock();
    int t=1;
    //cin>>t;
    while(t--)
        solve();
    //time_t TIME_TV=clock();
    //cerr<<(db)(TIME_TV-TIME_TU)/CLOCKS_PER_SEC<<endl;
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 7560 KB Output is correct
2 Correct 100 ms 8920 KB Output is correct
3 Correct 31 ms 9052 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 2392 KB Output is correct
4 Correct 1 ms 2600 KB Output is correct
5 Correct 29 ms 5724 KB Output is correct
6 Correct 34 ms 5872 KB Output is correct
7 Correct 4 ms 4700 KB Output is correct
8 Correct 17 ms 5468 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 4952 KB Output is correct
2 Correct 36 ms 6104 KB Output is correct
3 Correct 2 ms 4696 KB Output is correct
4 Correct 21 ms 5640 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 4952 KB Output is correct
2 Correct 39 ms 5968 KB Output is correct
3 Correct 7 ms 4696 KB Output is correct
4 Correct 35 ms 5972 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 5212 KB Output is correct
2 Correct 73 ms 8648 KB Output is correct
3 Correct 10 ms 5208 KB Output is correct
4 Correct 25 ms 8548 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 7356 KB Output is correct
2 Correct 67 ms 8776 KB Output is correct
3 Correct 38 ms 8708 KB Output is correct
4 Correct 10 ms 5212 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 7508 KB Output is correct
2 Correct 52 ms 8532 KB Output is correct
3 Correct 31 ms 8788 KB Output is correct
4 Correct 10 ms 5212 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 7504 KB Output is correct
2 Correct 68 ms 8660 KB Output is correct
3 Correct 24 ms 8028 KB Output is correct
4 Correct 42 ms 8348 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 7504 KB Output is correct
2 Correct 73 ms 8952 KB Output is correct
3 Correct 103 ms 9248 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 7764 KB Output is correct