| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 847511 | Ahmed57 | The short shank; Redemption (BOI21_prison) | C++17 | 0 ms | 0 KiB |
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>
using namespace std;
int n,k,T,arr[2000001];
struct node{
int cost = 0 , used = 0 , lazy = 0;
}seg[2000000*4];
node merg(node a,node b){
node ans;
ans.cost = min(a.cost,b.cost);
if(a.cost<b.cost)ans.used = a.used;
else if(a.cost>b.cost)ans.used = b.used;
else ans.used = max(a.used,b.used);
return ans;
}
void build(int p,int l,int r){
if(l==r){
seg[p].cost = 1e18 , seg[p].used = -1e18;
seg[p].lazy = 0;
return ;
}
int md = (l+r)/2;
build(p*2,l,md);build(p*2+1,md+1,r);
seg[p] = merg(seg[p*2],seg[p*2+1]);
}void prop(int p,int l,int r){
seg[p].cost+=seg[p].lazy;
if(l!=r){
seg[p*2].lazy+=seg[p].lazy;
seg[p*2+1].lazy+=seg[p].lazy;
}
seg[p].lazy = 0;
}
void update(int p,int l,int r,int lq,int rq,int val){
prop(p,l,r);
if(l>=lq&&r<=rq){
seg[p].lazy = val;
prop(p,l,r);
return ;
}
if(r<lq||l>rq)return ;
int md = (l+r)/2;
update(p*2,l,md,lq,rq,val);update(p*2+1,md+1,r,lq,rq,val);
seg[p] = merg(seg[p*2],seg[p*2+1]);
}
void po(int p,int l,int r,int idx,int vl1,int vl2){
prop(p,l,r);
if(l==r){
seg[p].cost = vl1;seg[p].used = vl2;
return ;
}
int md = (l+r)/2;
if(idx<=md)po(p*2,l,md,idx,vl1,vl2);
else po(p*2+1,md+1,r,idx,vl1,vl2);
seg[p] = merg(seg[p*2],seg[p*2+1]);
}
node query(int p,int l,int r,int lq,int rq){
prop(p,l,r);
if(l>=lq&&r<=rq)return seg[p];
int md = (l+r)/2;
if(rq<=md)return query(p*2,l,md,lq,rq);
else if(lq>md)return query(p*2+1,md+1,r,lq,rq);
return merg(query(p*2,l,md,lq,rq),query(p*2+1,md+1,r,lq,rq));
}
pair<long long,long long> solve(int mid){
stack<pair<pair<int,int>,int>> suf;
pair<int,int> dp[n+1];
dp[n] = {0,0};
build(1,0,n);
for(int i = n-1;i>=0;i--){
long long val = arr[i]-i;
int st = i+1;
while(!suf.empty()&&suf.top().first.first>=val){
int xd = suf.top().first.second;
int len1 = 0;
if(xd<=T){
len1 = min(suf.top().second,(T-xd+1));
}
int len2 = 0;
xd = arr[i];
if(xd+(st-i)<=T){
len2 = min(suf.top().second,(T-(xd+(st-i))+1));
}
if(len1<len2){
for(int e = len1+st;e<len2+st;e++){
update(1,0,n,e,n,1);
}
//update(1,0,n,len1+st,len2+st-1,1);
}
st+=suf.top().second;
suf.pop();
}
suf.push({{val,arr[i]},st-i});
update(1,0,n,i+1,n,(arr[i]<=T));
po(1,0,n,i,dp[i+1].first+(arr[i]<=T),dp[i+1].second);
node xd = query(1,0,n,i,n-1);
dp[i].first = xd.cost+mid;
dp[i].second = xd.used+1;
}
return {dp[0].first-mid,dp[0].second-1};
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>k>>T;
if(k==1){
int arr[n];
for(int i = 0;i<n;i++)cin>>arr[i];
int la = 0;
int pref[n] = {0};
for(int i = 0;i<n;i++){
if(i==0){
la = arr[i];
pref[i] = (arr[i]<=T);
}else{
if(la+1<=arr[i]){
la++;
pref[i] = (la<=T);
}else{
la = arr[i];
pref[i] = (arr[i]<=T);
}
pref[i] += pref[i-1];
}
}
stack<pair<pair<int,int>,int>> suf;int suff[n+1] = {0};
long long an = 0;
for(int i = n-1;i>=0;i--){
long long val = arr[i]-i;
an+=(arr[i]<=T);
int st = i+1;
while(!suf.empty()&&suf.top().first.first>=val){
int xd = suf.top().first.second;
int len1 = 0;
if(xd<=T){
len1 = min(suf.top().second,(T-xd+1));
}
int len2 = 0;
xd = arr[i];
if(xd+(st-i)<=T){
len2 = min(suf.top().second,(T-(xd+(st-i))+1));
}
an+=max(0ll,len2-len1);
st+=suf.top().second;
suf.pop();
}
suf.push({{val,arr[i]},st-i});
suff[i] = an;
}
int all = 1e18;
for(int i = 0;i<n;i++){
all = min(all,pref[i]+suff[i+1]);
}
cout<<all<<endl;
return 0;
}
for(int i = 0;i<n;i++)cin>>arr[i];
long long l = 0 , r = n , ans = -1e9;
while(l<=r){
long long mid = (l+r)/2;
pair<int,int> p = solve(mid);
if(p.second>=k){
ans = p.first-k*mid;
l = mid+1;
}else{
r = mid-1;
}
}cout<<ans<<endl;
}