Submission #429781

#	Time	Username	Problem	Language	Result	Execution time	Memory
429781		giorgikob	The short shank; Redemption (BOI21_prison)	C++14	0 / 100	144 ms	12272 KiB

prison

#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;

const int N = 2e6+50, mod = 998244353, K = 31;

int n,d,T;
int cnt = 0;
int L[N],R[N],B[N],A[N],gar[N],shig[N];
bool fix[N];
pair<int,int>mx[N*4];
int toadd[N*4];

inline void upd(int node,int tl,int tr,int l,int r,int val){

    if(tl > r || l > tr) return ;

    if(tl == tr){
        mx[node].ff += val;
        mx[node].ss = tl;
        return ;
    }

    if(l <= tl && tr <= r){
        mx[node].ff += val;
        toadd[node] += val;
        return ;
    }

    int mid = (tl+tr)/2;
    int left = node*2;
    int right = left+1;


    if(toadd[node]){
        toadd[left] += toadd[node];
        toadd[right] += toadd[node];
        mx[left].ff += toadd[node];
        mx[right].ff += toadd[node];
        toadd[node] = 0;
    }

    upd(left,tl,mid,l,r,val);
    upd(right,mid+1,tr,l,r,val);

    mx[node] = max(mx[left],mx[right]);
}

inline void upd1(int node,int tl,int tr,int l,int r){
    if(tl > r || l > tr) return ;
    if(tl == tr){
        mx[node].ff = L[tl+1] - L[tl];
        mx[node].ss = tl;
        return ;
    }

    int mid = (tl+tr)/2;
    int left = node*2;
    int right = left+1;

     if(toadd[node]){
        toadd[left] += toadd[node];
        toadd[right] += toadd[node];
        mx[left].ff += toadd[node];
        mx[right].ff += toadd[node];
        toadd[node] = 0;
    }

    upd1(left,tl,mid,l,r);
    upd1(right,mid+1,tr,l,r);

    mx[node] = max(mx[left],mx[right]);
}

inline void upd2(int node,int tl,int tr,int pos){

    if(tl == tr){
        mx[node] = {0,tl};
        return ;
    }

    int mid = (tl+tr)/2;
    int left = node*2;
    int right = left+1;


    if(toadd[node]){
        toadd[left] += toadd[node];
        toadd[right] += toadd[node];
        mx[left].ff += toadd[node];
        mx[right].ff += toadd[node];
        toadd[node] = 0;
    }

    if(pos <= mid){
        upd2(left,tl,mid,pos);
    } else {
        upd2(right,mid+1,tr,pos);
    }

    mx[node] = max(mx[left],mx[right]);
}

inline void test_case(){
    cin >> n >> d >> T;
    for(int i = 1; i <= n; i++){
        cin >> A[i];
        if(A[i] <= T){
            cnt++;
            L[cnt] = i;
            R[cnt] = min(n,T-A[i]+i);
            B[i]++;
            B[R[cnt]+1]--;
            if(L[cnt] <= R[cnt-1] && R[cnt-1] <= R[cnt]){
                R[cnt-1] = L[cnt]-1;
            }
        }
    }

    int answer = n;
    for(int i = 1; i <= n; i++){
        B[i] += B[i-1];
        if(B[i] == 0){
            answer--;
        }
    }

    gar[1] = 1;
    for(int i = 2; i <= cnt; i++){
        if(R[i] <= R[i-1]) gar[i] = gar[i-1]; else gar[i] = i;
    }

    shig[cnt] = cnt;
    for(int i = cnt-1; i >= 1; i--){
        if(R[i] >= R[i+1]) shig[i] = shig[i+1]; else shig[i] = i;
    }

    if(cnt <= d){
        cout << cnt << endl;
        return ;
    }

    for(int i = 1; i <= cnt; i++){
        int daf = R[i] - L[i];
        //cout << shig[i] << endl;
        //cout << L[i] << " " << R[i] << " " << shig[i] << endl;
        if(shig[i] != i) daf -= (R[i+1]-L[i+1]+1);
        //cout << daf << endl;
        upd(1,1,cnt,i,i,daf);
    }
    while(d--){
        pair<int,int> p = mx[1];
        int val = p.ff;
        int ind = p.ss;
        answer -= val;
        //cout << val << " " << ind << endl;
        if(fix[ind] == 1){
            upd2(1,1,cnt,ind);
        } else {
            upd2(1,1,cnt,ind);
            int val = R[ind]-R[shig[ind]];
            if(val)upd(1,1,cnt,ind,shig[ind],-val);
            if(gar[ind] < ind)upd1(1,1,cnt,gar[ind],ind-1);
            for(int i = gar[ind]; i <= ind; i++){
                fix[i] = 1;
            }
        }
    }

    cout << answer << endl;
}
 main(){
    ios::sync_with_stdio(0);

    int T = 1;
    //cin >> T;
    for(int i = 1; i <= T; i++){
        test_case();
    }
}

Compilation message (stderr)

prison.cpp:175:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  175 |  main(){
      |  ^~~~

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