oj.uz

Submission #740234

# Submission time Handle Problem Language Result Execution time Memory
740234 2023-05-12T07:55:07 Z bgnbvnbv Growing Trees (BOI11_grow) C++14
10 / 100
 154 ms 9492 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);
            // vi tri dau tien >= h
            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
0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 472 KB Output is correct
2 Correct 3 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 59 ms 1796 KB Output is correct
6 Incorrect 59 ms 1980 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 8912 KB Output is correct
2 Incorrect 126 ms 8436 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

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

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 9492 KB Output is correct