Submission #412887

#	Time	Username	Problem	Language	Result	Execution time	Memory
412887		nicolaalexandra	The short shank; Redemption (BOI21_prison)	C++14	80 / 100	2071 ms	209400 KiB

prison

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

vector <int> L[DIM];
deque <int> d;
int low[DIM],v[DIM],w[DIM],fth[DIM],taken[DIM],mars[DIM];
pair <int,int> intv[DIM];
int n,i,j,ans,D,t,k;

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

struct event{
    int val,idx,tip;
};

vector <event> events;

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

    int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
    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;
}

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;

}

inline int cmp (event a, event b){
    if (a.val == b.val){
        if (a.tip == b.tip && a.tip == 1)
            return intv[a.idx].second > intv[b.idx].second;

        return a.tip < b.tip; /// mai intai stergerile
    }
    return a.val < b.val;
}

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);
        }

    }

    for (i=1;i<=n;i++)
        if (low[i] != -1 && low[i] <= i-1){

            mars[low[i]]++, mars[i]--;
            //update (1,1,n,low[i],i-1,1);

            k++;
            intv[k] = make_pair(low[i],i-1);
            events.push_back({low[i],k,1});
            events.push_back({i,k,0});
        }

    for (i=1;i<=n;i++)
        mars[i] += mars[i-1];

    build (1,1,n);

    sort (events.begin(),events.end(),cmp);

    d.clear();
    int pos = 0;
    for (i=1;i<=n;i++){

        while (pos < events.size() && events[pos].val == i && events[pos].tip == 0){
            d.pop_back();
            pos++;
        }

        while (pos < events.size() && events[pos].val == i && events[pos].tip == 1){
            if (!d.empty())
                fth[events[pos].idx] = d.back();

            d.push_back(events[pos].idx);
            pos++;
        }

        if (!d.empty())
            w[i] = d.back();
    }


    for (;D--;){
        int poz = aint[1].poz;

        ans -= aint[1].maxi;

        int x = w[poz];
        while (x && !taken[x]){
            taken[x] = 1;
            update (1,1,n,intv[x].first,intv[x].second,-1);
            x = fth[x];
        }
    }

    cout<<ans;

  /*  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;
}

Compilation message (stderr)

prison.cpp: In function 'int main()':
prison.cpp:150:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |         while (pos < events.size() && events[pos].val == i && events[pos].tip == 0){
      |                ~~~~^~~~~~~~~~~~~~~
prison.cpp:155:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |         while (pos < events.size() && events[pos].val == i && events[pos].tip == 1){
      |                ~~~~^~~~~~~~~~~~~~~

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