Submission #409834

#	Time	Username	Problem	Language	Result	Execution time	Memory
409834		Ruxandra985	The short shank; Redemption (BOI21_prison)	C++14	100 / 100	1369 ms	313192 KiB

prison

#include <bits/stdc++.h>
#define DIMN 2000010
using namespace std;
int v[DIMN] , w[DIMN] , f[DIMN] , out[DIMN] , mark[DIMN] , tt[DIMN];
pair <int , int> ev[2 * DIMN] , now[DIMN] , cnt[DIMN];

vector <int> g[DIMN];
priority_queue <int> h;
priority_queue <pair <int , pair <int , int> > > h2;

priority_queue <pair <int , int > > h3;

struct interval{

    int poz , tip , idx;
} interv[2 * DIMN];

int cmp (interval x , interval y){

    if (x.poz != y.poz)
        return x.poz < y.poz;
    if (x.tip != y.tip)
        return x.tip < y.tip;

    return now[x.idx].second - now[x.idx].first < now[y.idx].second - now[y.idx].first;


}

void dfs (int nod){
    int i , vecin;
    cnt[nod] = make_pair(1 , nod);

    for (i = 0 ; i < g[nod].size() ; i++){
        vecin = g[nod][i];
        dfs(vecin);
        if (cnt[vecin].first + 1 > cnt[nod].first){
            cnt[nod] = make_pair(cnt[vecin].first + 1 , cnt[vecin].second);
        }
    }


}


int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , d , t , sol , i , elem = 0 , e = 0 , pmax , j , m , idk , poz , tip;
    int nod , vecin;
    fscanf (fin,"%d%d%d",&n,&d,&t);
    sol = 0;
    for (i = 1 ; i <= n ; i++){
        fscanf (fin,"%d",&v[i]);
        if (v[i] > t){
            w[++elem] = i;
        }
        else sol++;
    }

    for (i = 1 ; i <= n ; i++){

        if (v[i] < t){

            /// cauti in w intervalul de influenta
            pmax = min(n , i + t - v[i]);
            ev[++e] = make_pair(i , i);
            ev[++e] = make_pair(pmax + 1 , -i);

        }

    }

    sort (ev + 1 , ev + e + 1);

    i = 1;
    j = 1;
    m = 0;
    idk = 0;

    while (j <= elem){

        while (i <= e && ev[i].first <= w[j]){

            /// procesezi ev[i]
            if (ev[i].second > 0)
                h.push(ev[i].second);
            else {
                out[-ev[i].second] = 1; /// il scoti
            }

            i++;

        }

        /// acum vezi w[j] ce tata are

        while (!h.empty() && out[h.top()])
            h.pop();

        /// h.top() e tatal lui w[j]
        if (!h.empty()){
            now[++idk] = make_pair(h.top() , w[j]);
            interv[++m] = {h.top() , 1 , idk};
            interv[++m] = {w[j] , -1 , idk};
        }


        j++;

    }

    sort (interv + 1 , interv + m + 1 , cmp);


    for (i = 1 ; i <= m ; i++){

        poz = interv[i].poz;
        tip = interv[i].tip;

        if (tip == 1){
            h2.push(make_pair(-now[interv[i].idx].second , make_pair(poz , interv[i].idx)));
        }
        else { /// tip este -1

            /// intervalul meu este la top
            h2.pop();
            /// find interval care il contine

            if (!h2.empty()){
                /// top este tatal lui
                g[h2.top().second.second].push_back(interv[i].idx);
                tt[interv[i].idx] = h2.top().second.second;
                //printf ("%d %d\n" , h2.top().second.second , interv[i].idx);
            }

        }


    }


    for (i = 1 ; i <= idk ; i++){
        if (!tt[i]){
            dfs(i);
            h3.push(cnt[i]);
        }
    }


    for (j = 1 ; j <= d ; j++){

        while (mark[h3.top().second])
            h3.pop();

        nod = h3.top().second;
        h3.pop();

        while (!mark[nod]){

            mark[nod] = 1;

            for (i = 0 ; i < g[tt[nod]].size() ; i++){
                vecin = g[tt[nod]][i];
                if (!mark[vecin])
                    h3.push(cnt[vecin]);
            }


            nod = tt[nod];
        }

    }

    for (i = 1 ; i <= idk ; i++){
        if (!mark[i])
            sol++;
    }
    fprintf (fout,"%d",sol);

    return 0;
}

Compilation message (stderr)

prison.cpp: In function 'void dfs(int)':
prison.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (i = 0 ; i < g[nod].size() ; i++){
      |                  ~~^~~~~~~~~~~~~~~
prison.cpp: In function 'int main()':
prison.cpp:164:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |             for (i = 0 ; i < g[tt[nod]].size() ; i++){
      |                          ~~^~~~~~~~~~~~~~~~~~~
prison.cpp:52:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     fscanf (fin,"%d%d%d",&n,&d,&t);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
prison.cpp:55:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         fscanf (fin,"%d",&v[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