Submission #847510

#	Time	Username	Problem	Language	Result	Execution time	Memory
847510		Ahmed57	The short shank; Redemption (BOI21_prison)	C++17	80 / 100	1158 ms	18512 KiB

prison

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,k,T,arr[75001];
struct node{
    int cost = 0 , used = 0 , lazy = 0;
}seg[75000*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(){
    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;
}

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