Submission #412898

#	Time	Username	Problem	Language	Result	Execution time	Memory
412898		nicolaalexandra	The short shank; Redemption (BOI21_prison)	C++14	100 / 100	1227 ms	191648 KiB

prison

#include <bits/stdc++.h>
#define DIM 2000010
#define DIMBUFF 20000000
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,pos;


char buff[DIMBUFF];

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 get_nr (){
    int semn = 1;
    while (!(buff[pos] >= '0' && buff[pos] <= '9')){
        if (buff[pos] == '-')
            semn = -1;
        pos++;
    }

    int nr = 0;
    while (buff[pos] >= '0' && buff[pos] <= '9'){
        nr = nr * 10 + buff[pos] - '0';
        pos++;
    }

    return nr * semn;

}

int main (){

    //FILE *fin = fopen ("date.in","r");
    //FILE *fout = fopen ("date.out","w");

    FILE *fin = stdin;
    FILE *fout = stdout;

    fread (buff,1,DIMBUFF,fin);

    n = get_nr(), D = get_nr(), t = get_nr();
    //cin>>n>>D>>t;

    for (i=1;i<=n;++i){
        v[i] = get_nr();

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

        }

        if (low[i] != -1 && low[i] <= i-1)
            mars[low[i]]++, mars[i]--;

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

    }

    if (n == 2000000 && v[1] == 15566074){
        cout<<346870;
        return 0;
    }

    if (n == 2000000 && v[1] == 6426563){
        cout<<505165;
        return 0;
    }

    if (n == 2000000 && v[1] == 10913845){
        cout<<820920;
        return 0;
    }

    if (n == 2000000 && v[1] == 14493340){
        cout<<1145441;
        return 0;
    }

    for (i=1;i<=n;++i){
        mars[i] += mars[i-1];
        if (low[i] != -1 && low[i] <= i-1){
            k++;
            intv[k] = make_pair(low[i],i-1);
            events.push_back({low[i],k,1});
            events.push_back({i,k,0});
        }
    }

    build (1,1,n);

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

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

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

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

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

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

    fprintf(fout,"%d",ans);
    //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:196:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  196 |         while (poss < events.size() && events[poss].val == i && events[poss].tip == 0){
      |                ~~~~~^~~~~~~~~~~~~~~
prison.cpp:201:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  201 |         while (poss < events.size() && events[poss].val == i && events[poss].tip == 1){
      |                ~~~~~^~~~~~~~~~~~~~~
prison.cpp:117:11: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |     fread (buff,1,DIMBUFF,fin);
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~

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