Submission #1039340

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039340		happy_node	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	1521 ms	180432 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];

struct segtree {
        pair<int,int> t[4*MX];  
        int lazy[4*MX];

        void push(int v, int l, int r) {
                if(lazy[v]==0) return;
                t[v].first+=lazy[v];
                if(l!=r) {
                        lazy[2*v]+=lazy[v];
                        lazy[2*v+1]+=lazy[v];
                }
                lazy[v]=0;
        }

        void upd(int v, int l, int r, int ql, int qr, int x) {
                push(v,l,r);
                if(r<ql || qr<l) return;
                if(ql<=l && r<=qr) {
                        lazy[v]+=x;
                        push(v,l,r);
                        return;
                }
                int m=(l+r)/2;
                upd(2*v,l,m,ql,qr,x);
                upd(2*v+1,m+1,r,ql,qr,x);
                t[v]=max(t[2*v],t[2*v+1]);
        }

        pair<int,int> que(int v, int l, int r, int ql, int qr) {
                push(v,l,r);
                if(r<ql || qr<l) return {0,0};
                if(ql<=l && r<=qr) return t[v];
                int m=(l+r)/2;
                return max(que(2*v,l,m,ql,qr),que(2*v+1,m+1,r,ql,qr));
        }

        void prep() {
                for(int i=0;i<4*MX;i++) {
                        t[i]={-2e9,-2e9};
                }
        }

        void build(int v, int l, int r) {
                if(l>r) return;
                if(l==r) {
                        t[v]={0,l};
                        return;
                }
                int m=(l+r)/2;
                build(2*v,l,m);
                build(2*v+1,m+1,r);
                t[v]=max(t[2*v],t[2*v+1]);
        }
} st;

struct segtree2 {
        pair<int,int> t[4*MX];

        void upd(int v, int l, int r, int pos, int val) {
                if(pos<l || pos>r) return;
                if(l==r) {
                        t[v]={val,pos};
                        return;
                }
                int m=(l+r)/2;
                if(pos<=m)
                        upd(2*v,l,m,pos,val);
                else 
                        upd(2*v+1,m+1,r,pos,val);
                t[v]=min(t[2*v],t[2*v+1]);
        }           

        pair<int,int> que(int v, int l, int r, int ql, int qr) {
                if(r<ql || qr<l) return {1e9,1e9};
                if(ql<=l && qr>=r) return t[v];
                int m=(l+r)/2;
                return min(que(2*v,l,m,ql,qr),que(2*v+1,m+1,r,ql,qr));
        }    

        void prep() {
                for(int i=0;i<4*MX;i++) {
                        t[i]={1e9,1e9};
                }
        }

        void build(int v, int l, int r) {
                if(l>r) return;
                if(l==r) {
                        if(B[l]>0) t[v]={B[l],l};
                        else t[v]={1e9,l};
                        return;
                }
                int m=(l+r)/2;
                build(v*2,l,m);
                build(v*2+1,m+1,r);
                t[v]=min(t[2*v],t[2*v+1]);
        }
} tt;

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];

        st.prep();
        st.build(1,1,N);

        vector<int> stk;
        for(int i=N;i>=1;i--) {
                if(A[i]<=T) {
                        int cur=A[i];
                        B[i]=i;
                        while(stk.size() && stk.back()-i+A[i]<=T) {
                                B[stk.back()]=i;
                                st.upd(1,1,N,i,stk.back(),1);
                                stk.pop_back();
                        }
                } else {
                        stk.push_back(i);
                }
        }
                
        tt.prep();
        tt.build(1,1,N);

        int ans=0;
        for(int i=1;i<=N;i++) {
                if(B[i]>0) ans++;
                else st.upd(1,1,N,i,i,-1e9);
        }

        while(D>0) {
                D--;
                auto [v,p]=st.que(1,1,N,1,N);
                if(v<=0) break;

                while(true) {
                        auto [v0,p0]=tt.que(1,1,N,p,N);
                        if(v0>p) break; 
                        st.upd(1,1,N,v0,p0,-1);
                        tt.upd(1,1,N,p0,1e9);

                }
                ans-=v;
        }

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

Compilation message (stderr)

prison.cpp: In function 'int main()':
prison.cpp:123:29: warning: unused variable 'cur' [-Wunused-variable]
  123 |                         int cur=A[i];
      |                             ^~~

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