Submission #740240

#	Time	Username	Problem	Language	Result	Execution time	Memory
740240		bgnbvnbv	Growing Trees (BOI11_grow)	C++14	0 / 100	72 ms	131072 KiB

grow

#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 (stderr)

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;
      |            ~^~
grow.cpp: In function 'int main()':
grow.cpp:126:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |     freopen(TASKNAME".INP","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
grow.cpp:127:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |     freopen(TASKNAME".OUT","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10