Submission #744919

#	Time	Username	Problem	Language	Result	Execution time	Memory
744919		bgnbvnbv	The short shank; Redemption (BOI21_prison)	C++14	80 / 100	2050 ms	177192 KiB

prison

#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=int;
const ll maxN=2e6+10;
const ll inf=1e8;

struct node
{
    ll pos,val;
    node ()
    {
        val=inf;
        pos=0;
    }
    node operator+(const node&o)
    {
        node ans;
        if(val<=o.val) ans.val=val,ans.pos=pos;
        else  ans=o;
        return ans;
    }
};
ll n,a[maxN];
deque<int>dq;
struct IT1
{
    node st[4*maxN];
    ll lazy[4*maxN];
    void build(ll id=1,ll l=1,ll r=n)
    {
        if(l==r)
        {
            st[id].val=0;
            st[id].pos=l;
            return;
        }
        ll mid=l+r>>1;
        build(id*2,l,mid);
        build(id*2+1,mid+1,r);
        st[id]=st[id*2]+st[id*2+1];
    }
    void down(ll id)
    {
        ll &x=lazy[id];
        st[id*2].val+=x;
        st[id*2+1].val+=x;
        lazy[id*2]+=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+=val;
            lazy[id]+=val;
            return;
        }
        ll mid=l+r>>1;
        down(id);
        update(i,j,val,id*2+1,mid+1,r);
        update(i,j,val,id*2,l,mid);
        st[id]=st[id*2]+st[id*2+1];
    }
    node get()
    {
        return st[1];
    }
}t1;
struct IT2
{
    node st[4*maxN];
    void update(ll pos,ll val,ll id=1,ll l=1,ll r=n)
    {
        if(l==r)
        {
            st[id].val=val;
            st[id].pos=l;
            return;
        }
        ll mid=l+r>>1;
        if(pos<=mid) update(pos,val,id*2,l,mid);
        else update(pos,val,id*2+1,mid+1,r);
        st[id]=st[id*2]+st[id*2+1];
    }
    node get(ll i,ll j,ll id=1,ll l=1,ll r=n)
    {
        if(j<l||r<i) return node();
        if(i<=l&&r<=j) return st[id];
        ll mid=l+r>>1;
        return get(i,j,id*2,l,mid)+get(i,j,id*2+1,mid+1,r);
    }
}t2;
ll t;
ll bs(ll x)
{
    ll low=0,high=(ll)dq.size()-1;
    while(low<=high)
    {
        ll mid=low+high>>1;
        if(a[dq[mid]]+x<=t) low=mid+1;
        else high=mid-1;
    }
    return high;
}
ll d;
ll l[maxN];
ll ans=0;
void solve()
{
    cin >> n >> d >> t;
    t1.build();
    //t2.build();
    for(int i=1;i<=n;i++) cin >>a[i],a[i]-=i;
    for(int i=1;i<=n;i++)
    {
        while(dq.size()>0&&a[i]<=a[dq.back()])
        {
            dq.pop_back();
        }
        dq.pb(i);
        l[i]=bs(i);
        if(l[i]<0) l[i]=i;
        else l[i]=dq[l[i]],ans++;
        t1.update(l[i]+1,i,-1);
        t2.update(i,l[i]+1);
        l[i]++;
    }
    d=min(d,n-1);
    //cout << ans << '\n';
    while(d--)
    {
        ans+=t1.get().val;
        ll pos=t1.get().pos;
        while(true)
        {
            ll x=t2.get(pos,n).pos;
            if(l[x]>pos) break;
            t1.update(l[x],x,1);
            l[x]=inf;
            t2.update(x,l[x]);
        }
    }
    cout << ans;
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message (stderr)

prison.cpp: In member function 'void IT1::build(ll, ll, ll)':
prison.cpp:43:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |         ll mid=l+r>>1;
      |                ~^~
prison.cpp: In member function 'void IT1::update(ll, ll, ll, ll, ll, ll)':
prison.cpp:66:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |         ll mid=l+r>>1;
      |                ~^~
prison.cpp: In member function 'void IT2::update(ll, ll, ll, ll, ll)':
prison.cpp:88:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |         ll mid=l+r>>1;
      |                ~^~
prison.cpp: In member function 'node IT2::get(ll, ll, ll, ll, ll)':
prison.cpp:97:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   97 |         ll mid=l+r>>1;
      |                ~^~
prison.cpp: In function 'll bs(ll)':
prison.cpp:107:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  107 |         ll mid=low+high>>1;
      |                ~~~^~~~~

• Subtask 1: 15 / 15
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 25 / 25
• Subtask 6: 0 / 20