Submission #411652

#	Time	Username	Problem	Language	Result	Execution time	Memory
411652		nicolaalexandra	The short shank; Redemption (BOI21_prison)	C++14	55 / 100	2089 ms	72412 KiB

prison

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

vector <int> L[DIM];
deque <int> d;
int low[DIM],v[DIM];
int n,i,j,ans,D,t;

struct segment_tree{
    int maxi,poz,lazy;
} aint[DIM*4];

void build (int nod, int st, int dr){
    if (st == dr){
        aint[nod].poz = st;
        return;
    }
    int mid = (st+dr)>>1;
    build (nod<<1,st,mid);
    build ((nod<<1)|1,mid+1,dr);
    aint[nod].poz = aint[nod<<1].poz;
}

void update_lazy (int nod, int st, int dr){
    if (!aint[nod].lazy)
        return;
    if (st != dr){
        int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
        aint[fiu_st].maxi += aint[nod].lazy;
        aint[fiu_st].lazy += aint[nod].lazy;

        aint[fiu_dr].maxi += aint[nod].lazy;
        aint[fiu_dr].lazy += aint[nod].lazy;
    }
    aint[nod].lazy = 0;
}

void update (int nod, int st, int dr, int x, int y, int val){
    update_lazy (nod,st,dr);
    if (x <= st && dr <= y){
        aint[nod].maxi += val;
        aint[nod].lazy += val;
        update_lazy (nod,st,dr);
        return;
    }

    int mid = (st+dr)>>1;
    if (x <= mid)
        update (nod<<1,st,mid,x,y,val);
    if (y > mid)
        update ((nod<<1)|1,mid+1,dr,x,y,val);

    int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
    update_lazy (fiu_st,st,mid);
    update_lazy (fiu_dr,mid+1,dr);

    if (aint[fiu_st].maxi > aint[fiu_dr].maxi)
        aint[nod].maxi = aint[fiu_st].maxi, aint[nod].poz = aint[fiu_st].poz;
    else aint[nod].maxi = aint[fiu_dr].maxi, aint[nod].poz = aint[fiu_dr].poz;

}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>D>>t;
    for (i=1;i<=n;i++)
        cin>>v[i];


    for (i=1;i<=n;i++){
        while (!d.empty() && v[d.back()] + i - d.back() - t > 0)
            d.pop_back();

        if (v[i] <= t){
            low[i] = -1;
            ans++;


        } else {

            if (d.empty())
                low[i] = -1;
            else {
                ans++;
                low[i] = d.back();
            }

        }

        /// trb sa mai scot din stiva in caz ca o pozitie si ar pierde influenta pt ca
        /// vine alta care incepe un interval nou
        if (v[i] < t){
            while (!d.empty() && v[d.back()] - d.back() >= v[i] - i)
                d.pop_back();

            d.push_back(i);
        }

    }


    build (1,1,n);
    for (i=1;i<=n;i++)
        if (low[i] != -1 && low[i] <= i-1){
            update (1,1,n,low[i],i-1,1);
            L[low[i]].push_back(i-1);
        }

    for (i=1;i<=n;i++)
        sort (L[i].begin(),L[i].end());

    for (int pas=1;pas<=D;pas++){
        int poz = aint[1].poz;

        ans -= aint[1].maxi;

        for (i=1;i<=poz;i++)
            while (L[i].size() && L[i].back() >= poz){
                update (1,1,n,i,L[i].back(),-1);
                L[i].pop_back();
            }
    }

    cout<<ans;

    return 0;
}

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