oj.uz

Submission #740241

# Submission time Handle Problem Language Result Execution time Memory
740241 2023-05-12T08:11:41 Z bgnbvnbv Growing Trees (BOI11_grow) C++14
100 / 100
 163 ms 9076 KB 
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,c[maxN],st[4*maxN],mn[4*maxN];
void build(ll id=1,ll l=1,ll r=n)
{
    if(l==r)
    {
        st[id]=c[l];
        mn[id]=c[l];
        return;
    }
    ll mid=l+r>>1;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    st[id]=max(st[id],st[id*2+1]);
    mn[id]=min(mn[id*2],mn[id*2+1]);
}
ll lazy[4*maxN];
void down(ll id)
{
    ll &x=lazy[id];
    st[id*2]+=x;
    mn[id*2]+=x;
    lazy[id*2]+=x;
    st[id*2+1]+=x;
    mn[id*2+1]+=x;
    lazy[id*2+1]+=x;
    x=0;
}
void update(ll i,ll j,ll val,ll id=1,ll l=1,ll r=n)
{
    if(j<l||r<i) return;
    if(i<=l&&r<=j)
    {
        st[id]+=val;
        mn[id]+=val;
        lazy[id]+=val;
        return;
    }
    down(id);
    ll mid=l+r>>1;
    update(i,j,val,id*2,l,mid);
    update(i,j,val,id*2+1,mid+1,r);
    st[id]=max(st[id*2],st[id*2+1]);
    mn[id]=min(mn[id*2],mn[id*2+1]);
}
ll get(ll pos,ll id=1,ll l=1,ll r=n)
{
    if(l==r)
    {
        return st[id];
    }
    down(id);
    ll mid=l+r>>1;
    if(pos<=mid) return get(pos,id*2,l,mid);
    return get(pos,id*2+1,mid+1,r);
}
ll bs1(ll val,ll id=1,ll l=1,ll r=n)
{
    if(st[id]<val) return r+1;
    if(l==r) return l;
    down(id);
    ll mid=l+r>>1;
    ll pos=bs1(val,id*2,l,mid);
    if(pos==mid+1) return bs1(val,id*2+1,mid+1,r);
    return pos;
}
ll bs2(ll val,ll id=1,ll l=1,ll r=n)
{
    if(mn[id]>val) return l-1;
    if(l==r) return l;
    down(id);
    ll mid=l+r>>1;
    ll pos=bs2(val,id*2+1,mid+1,r);

    if(pos==mid) return bs2(val,id*2,l,mid);
    return pos;
}
ll m;
void solve()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> c[i];
    sort(c+1,c+n+1);
    build();
    for(int i=1;i<=m;i++)
    {
        char t;
        cin >> t;
        if(t=='F')
        {
            ll c,h;
            cin >> c >> h;
            ll l=bs1(h);
            if(l>n) continue;
            ll r=l+c-1;
            r=min(r,n);
            ll x=get(r);
            ll fi=bs1(x);
            ll se=bs2(x);
            ll num=r-fi+1;
            update(l,fi-1,1);
            update(se-num+1,se,1);
        }
        else
        {
            ll l,r;
            cin >> l>> r;
            cout << bs2(r)-bs1(l)+1<<'\n';
        }
    }
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message

grow.cpp: In function 'void build(ll, ll, ll)':
grow.cpp:22:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |     ll mid=l+r>>1;
      |            ~^~
grow.cpp: In function 'void update(ll, ll, ll, ll, ll, ll)':
grow.cpp:51:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |     ll mid=l+r>>1;
      |            ~^~
grow.cpp: In function 'll get(ll, ll, ll, ll)':
grow.cpp:64:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |     ll mid=l+r>>1;
      |            ~^~
grow.cpp: In function 'll bs1(ll, ll, ll, ll)':
grow.cpp:73:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |     ll mid=l+r>>1;
      |            ~^~
grow.cpp: In function 'll bs2(ll, ll, ll, ll)':
grow.cpp:83:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |     ll mid=l+r>>1;
      |            ~^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 7364 KB Output is correct
2 Correct 134 ms 8820 KB Output is correct
3 Correct 161 ms 8784 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 52 ms 888 KB Output is correct
6 Correct 59 ms 1088 KB Output is correct
7 Correct 6 ms 852 KB Output is correct
8 Correct 31 ms 1516 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 1140 KB Output is correct
2 Correct 53 ms 2072 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 37 ms 1728 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 1208 KB Output is correct
2 Correct 62 ms 2084 KB Output is correct
3 Correct 10 ms 852 KB Output is correct
4 Correct 56 ms 2116 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 4120 KB Output is correct
2 Correct 128 ms 8372 KB Output is correct
3 Correct 16 ms 2388 KB Output is correct
4 Correct 115 ms 8316 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 7088 KB Output is correct
2 Correct 154 ms 8516 KB Output is correct
3 Correct 141 ms 8536 KB Output is correct
4 Correct 15 ms 2420 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 7296 KB Output is correct
2 Correct 83 ms 8432 KB Output is correct
3 Correct 148 ms 8724 KB Output is correct
4 Correct 15 ms 2392 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 7312 KB Output is correct
2 Correct 134 ms 7252 KB Output is correct
3 Correct 32 ms 7984 KB Output is correct
4 Correct 90 ms 8176 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 7368 KB Output is correct
2 Correct 123 ms 8788 KB Output is correct
3 Correct 163 ms 9076 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 7656 KB Output is correct