Submission #744938

#	Time	Username	Problem	Language	Result	Execution time	Memory
744938		bgnbvnbv	The short shank; Redemption (BOI21_prison)	C++14	100 / 100	1750 ms	120372 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
{
    ll st[4*maxN];
    ll lazy[4*maxN];
    void down(ll id)
    {
        ll &x=lazy[id];
        st[id*2]+=x;
        st[id*2+1]+=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;
            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]=min(st[id*2],st[id*2+1]);
    }
    pli get()
    {
        ll x=st[1];
        ll id=1,l=1,r=n;
        while(true)
        {
            if(l==r) return {x,l};
            ll mid=l+r>>1;
            down(id);
            if(st[id*2]>x)
            {
                id=id*2+1;
                l=mid+1;
            }
            else
            {
                id=id*2;
                r=mid;
            }
        }
    }
}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 d;
ll ans=0;
void solve()
{
    cin >> n >> d >> t;
//    t1.build();
    for(int i=1;i<=n;i++) cin >>a[i],a[i]-=i;
    ll l;
    for(int i=1;i<=n;i++)
    {
        while(dq.size()>0&&a[i]<=a[dq.back()])
        {
            dq.pop_back();
        }
        dq.pb(i);
        while(dq.size()>0&&i+a[dq.back()]>t) dq.pop_back();
        if(dq.size()==0) l=i;
        else l=dq.back(),ans++;
        t1.update(l+1,i,-1);
        t2.update(i,l+1);
        l++;
    }
    d=min(d,n-1);
    node vd;
    ll cur;
    while(d--)
    {
        cur=ans;
        ans+=t1.get().fi;
        if(cur==ans) break;
        ll pos=t1.get().se;
        while(true)
        {
            vd=t2.get(pos,n);
            ll x=vd.pos;
            l=vd.val;
            if(l>pos) break;
            t1.update(l,x,1);
            l=inf;
            t2.update(x,l);
        }
    }
    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::update(ll, ll, ll, ll, ll, ll)':
prison.cpp:52:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |         ll mid=l+r>>1;
      |                ~^~
prison.cpp: In member function 'std::pair<int, int> IT1::get()':
prison.cpp:65:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |             ll mid=l+r>>1;
      |                    ~^~
prison.cpp: In member function 'void IT2::update(ll, ll, ll, ll, ll)':
prison.cpp:91:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |         ll mid=l+r>>1;
      |                ~^~
prison.cpp: In member function 'node IT2::get(ll, ll, ll, ll, ll)':
prison.cpp:100:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |         ll mid=l+r>>1;
      |                ~^~

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