제출 #489492

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
489492		cpp219	The short shank; Redemption (BOI21_prison)	C++14	0 / 100	455 ms	83776 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;
    if (!cond){
        st[cond][id*2] += t; st[cond][id*2 + 1] += t;
    }
    else{
        st[cond][id*2] += t*(mid - l + 1);
        st[cond][id*2 + 1] += t*(r - mid);
    }
}

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] = st[cond][id*2] + st[cond][id*2 + 1];
}

ll Walksum(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 Walksum(cond,id*2,l,mid);
    return Walksum(cond,id*2 + 1,mid + 1,r);
}
ll Getsum(){
    return Walksum(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;
}

vector<ll> g[N];
ll cur = 1;

int main(){
    ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    #define task "tst"
    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];
        if (a[i] <= t) g[min(n,i + t - a[i])].push_back(i);
    }
    set<ll> s;
    for (ll i = n;i > 0;i--){
        for (auto j : g[i]) s.insert(j);
        s.erase(i);
        if (a[i] <= t || s.size()) ans++;
        if (s.size() && a[i] > t) low[i] = *s.rbegin();
        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]<<" "; debug(ans);
    //return 0;
    while(D--){
        ll best = Getsum();
        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--;
        }
    }
    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
*/

컴파일 시 표준 에러 (stderr) 메시지

prison.cpp: In function 'int main()':
prison.cpp:74:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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