This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 "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];
while(!S.empty() && a[i] - i < a[S.top()] - S.top()) S.pop();
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);
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]<<" "; //debug(ans);
//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);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |