Submission #1106407

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106407		alexdd	The short shank; Redemption (BOI21_prison)	C++17	70 / 100	1505 ms	524288 KiB

prison

#include <bits/stdc++.h>
using namespace std;
int n,d,lim;
int t[2000005];
bool blocat[2000005];
int tole[2000005];

pair<int,int> aint[4200000];
int lazy[4200000];
void build(int nod, int st, int dr)
{
    if(st==dr)
    {
        aint[nod] = {0,st};
        return;
    }
    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
    aint[nod] = max(aint[nod*2], aint[nod*2+1]);
}
void propagate(int nod)
{
    lazy[nod*2] += lazy[nod];
    lazy[nod*2+1] += lazy[nod];
    aint[nod*2].first += lazy[nod];
    aint[nod*2+1].first += lazy[nod];
    lazy[nod]=0;
}
void upd(int nod, int st, int dr, int le, int ri, int newv)
{
    if(le>ri)
        return;
    if(le==st && dr==ri)
    {
        aint[nod].first += newv;
        lazy[nod] += newv;
        return;
    }
    propagate(nod);
    int mij=(st+dr)/2;
    upd(nod*2,st,mij,le,min(mij,ri),newv);
    upd(nod*2+1,mij+1,dr,max(mij+1,le),ri,newv);
    aint[nod] = max(aint[nod*2], aint[nod*2+1]);
}

set<int> s[4200000];
void baga_s(int nod, int st, int dr, int le, int ri, int id)
{
    if(le>ri)
        return;
    if(le==st && dr==ri)
    {
        s[nod].insert(id);
        return;
    }
    int mij=(st+dr)/2;
    baga_s(nod*2,st,mij,le,min(mij,ri),id);
    baga_s(nod*2+1,mij+1,dr,max(mij+1,le),ri,id);
}
void scoate_s(int nod, int st, int dr, int le, int ri, int id)
{
    if(le>ri)
        return;
    if(le==st && dr==ri)
    {
        assert(s[nod].find(id)!=s[nod].end());
        s[nod].erase(id);
        return;
    }
    int mij=(st+dr)/2;
    scoate_s(nod*2,st,mij,le,min(mij,ri),id);
    scoate_s(nod*2+1,mij+1,dr,max(mij+1,le),ri,id);
}
vector<int> aux;
void get_s(int nod, int st, int dr, int poz)
{
    for(auto x:s[nod])
        aux.push_back(x);
    if(st==dr)
        return;
    int mij=(st+dr)/2;
    if(poz<=mij) get_s(nod*2,st,mij,poz);
    else get_s(nod*2+1,mij+1,dr,poz);
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>d>>lim;
    build(1,1,n);
    deque<int> dq;
    int rez=0;
    for(int i=1;i<=n;i++)
    {
        cin>>t[i];
        while(!dq.empty() && t[i] - i <= t[dq.back()] - dq.back())
            dq.pop_back();
        dq.push_back(i);

        while(!dq.empty() && t[dq.back()] - dq.back() > lim - i)
            dq.pop_back();
        if(dq.empty())
            tole[i] = n+1;
        else
            tole[i] = dq.back();
        upd(1,1,n,tole[i],i-1,+1);
        baga_s(1,1,n,tole[i],i-1,i);
        if(tole[i]!=n+1)
            rez++;
    }
    for(int pas=1;pas<=d;pas++)
    {
        if(aint[1].first==0)
            break;
        rez -= aint[1].first;
        int unde = aint[1].second;
        blocat[unde]=1;
        /*for(int i=unde+1;i<=n;i++)
        {
            if(tole[i]<=unde)
            {
                upd(1,1,n,tole[i],i-1,-1);
                tole[i] = n+1;
            }
        }*/
        aux.clear();
        get_s(1,1,n,unde);
        for(int x:aux)
        {
            upd(1,1,n,tole[x],x-1,-1);
            scoate_s(1,1,n,tole[x],x-1,x);
        }
    }
    cout<<rez;
    return 0;
}
/*
pentru fiecare pozitie i ne intereseaza doar cea mai din dreapta pozitie j aflata in stanga ei care respecta
j <= i
t[j] + (i-j) <= lim
t[j] - j <= lim - i

*/

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