Submission #489527

#	Time	Username	Problem	Language	Result	Execution time	Memory
489527		cpp219	The short shank; Redemption (BOI21_prison)	C++14	80 / 100	2017 ms	82456 KiB

prison

#include<bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
#define debug(y) cout<<y,exit(0)
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 2e6 + 9;
const ll inf = 1e9 + 7;

ll n,D,t,a[N],low[N],ans;
ll st[2][4*N],lazy[2][4*N];

void Pass(ll cond,ll id,ll l,ll r){
    ll t = lazy[cond][id]; lazy[cond][id] = 0;
    ll mid = (l + r)/2;
    lazy[cond][id*2] += t; lazy[cond][id*2 + 1] += t;
    st[cond][id*2] += t; st[cond][id*2 + 1] += t;
}

void upd(ll cond,ll id,ll l,ll r,ll u,ll v,ll val){
    if (v < l||r < u) return;
    if (u <= l&&r <= v){
        st[cond][id] += val; lazy[cond][id] += val;
        return;
    }
    ll mid = (l + r)/2; Pass(cond,id,l,r);
    upd(cond,id*2,l,mid,u,v,val); upd(cond,id*2 + 1,mid + 1,r,u,v,val);
    if (!cond) st[cond][id] = min(st[cond][id*2],st[cond][id*2 + 1]);
    else st[cond][id] = max(st[cond][id*2],st[cond][id*2 + 1]);
}

ll Walkmax(ll cond,ll id,ll l,ll r){
    if (l == r) return l;
    ll mid = (l + r)/2; Pass(cond,id,l,r);
    if (st[cond][id*2] >= st[cond][id*2 + 1])
        return Walkmax(cond,id*2,l,mid);
    return Walkmax(cond,id*2 + 1,mid + 1,r);
}
ll Getmax(){
    return Walkmax(1,1,1,n);
}

ll Walkmin(ll cond,ll id,ll l,ll r,ll val){
    if (l == r){
        if (st[cond][id] > val) return inf;
        return l;
    }
    ll mid = (l + r)/2; Pass(cond,id,l,r);
    if (st[cond][id*2] <= st[cond][id*2 + 1])
        return Walkmin(cond,id*2,l,mid,val);
    return Walkmin(cond,id*2 + 1,mid + 1,r,val);
}
ll Getmin(ll best){
    upd(0,1,1,n,1,best,inf);
    ll kq = Walkmin(0,1,1,n,best); upd(0,1,1,n,1,best,-inf);
    return kq;
}

stack<ll> S;

int main(){
    ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    #define task "test"
    if (fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        //freopen(task".out","w",stdout);
    }
    cin>>n>>D>>t; fill(low,low + n + 1,inf);
    for (ll i = 1;i <= n;i++){
        cin>>a[i];
        while(!S.empty() && a[S.top()] - S.top() + i > t) S.pop();
        //if (i == 3) debug(S.top());
        if (!S.empty()){
            if (a[S.top()] - S.top() + i <= t) low[i] = S.top();
            if (a[i] <= t) low[i] = inf;
        }
        ans += (a[i] <= t || low[i] != inf);
        while(!S.empty() && a[i] - i < a[S.top()] - S.top()) S.pop();
        S.push(i);
        upd(1,1,1,n,low[i],i - 1,1);
        upd(0,1,1,n,i,i,low[i]);
    }
    //for (ll i = 1;i <= n;i++) cout<<low[i]<<" "; return 0;
    while(D--){
        ll best = Getmax();
        if (!best) break;
        while(1){
            ll now = Getmin(best);
            if (now > n) break;
            upd(1,1,1,n,low[now],now - 1,-1);
            upd(0,1,1,n,now,now,inf); ans--;
        }

        //debug(Getmax());
    }
    cout<<ans;
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* DON'T GET STUCK ON ONE APPROACH
*/

Compilation message (stderr)

prison.cpp: In function 'void Pass(int, int, int, int)':
prison.cpp:17:8: warning: unused variable 'mid' [-Wunused-variable]
   17 |     ll mid = (l + r)/2;
      |        ^~~
prison.cpp: In function 'int main()':
prison.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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