Submission #1029162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029162		happy_node	The short shank; Redemption (BOI21_prison)	C++17	55 / 100	2072 ms	13396 KiB

prison

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MX=2e6+5;

int N,D,T;

int A[MX],B[MX];
bool C[MX];

int main() {
        cin.tie(0); ios_base::sync_with_stdio(0);

        cin>>N>>D>>T;

        for(int i=1;i<=N;i++) {
                cin>>A[i];
                B[i]=A[i]-i;
        }

        for(int d=0;d<D;d++) {
                vector<int> stk;

                vector<int> cnt(N+1);
                for(int i=1;i<=N;i++) {
                        while(stk.size() && B[stk.back()]>=B[i]) stk.pop_back();
                        if(A[i]<=T) {
                                stk.push_back(i);
                        } else {
                                int l=0,r=stk.size()-1,p=-1;
                                while(l<=r) {
                                        int m=(l+r)/2;
                                        if(A[stk[m]]+i-stk[m]<=T) {
                                                l=m+1,p=m;
                                        } else {
                                                r=m-1;
                                        }
                                }
                                if(p!=-1) {
                                        cnt[stk[p]]+=1;
                                        cnt[i]-=1;
                                }
                        }

                        if(C[i]) stk.clear();
                }

                int arg=0;
                for(int i=1;i<=N;i++) {
                        cnt[i]+=cnt[i-1];
                        if(cnt[i]>cnt[arg] && A[i]<=T) arg=i;
                }

                C[arg]=true;
        }

        vector<int> stk;

        int ans=0;
        for(int i=1;i<=N;i++) {
                while(stk.size() && B[stk.back()]>=B[i]) stk.pop_back();

                if(A[i]<=T) {
                        ans++;
                        stk.push_back(i);
                } else {
                        if(stk.size() && A[stk.front()]+i-stk.front()<=T) ans++;
                }

                if(C[i]) stk.clear();
        }

        cout<<ans<<'\n';
}

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