Submission #402828

#	Time	Username	Problem	Language	Result	Execution time	Memory
402828		Ruxandra985	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	1793 ms	63736 KiB

sortbooks

#include <bits/stdc++.h>
#define DIMN 1000010
using namespace std;

struct segm{

    int maxi , pmaxi , sorted , maxi2 , pmaxi2;
    int altm , paltm;

} aint[4 * DIMN];

int v[DIMN];

void build (int nod , int st , int dr){
    int mid = (st + dr)/2;

    if (st == dr){
        aint[nod].maxi = v[st];
        aint[nod].pmaxi = st;
        aint[nod].maxi2 = -1;
        aint[nod].pmaxi2 = DIMN + 10;
        aint[nod].altm = -1;
        aint[nod].paltm = DIMN + 10;
        aint[nod].sorted = 1;
        return;
    }

    build (2 * nod , st , mid);
    build (2 * nod + 1 , mid + 1 , dr);

    if (aint[2 * nod].maxi >= aint[2 * nod + 1].maxi){
        aint[nod].maxi = aint[2 * nod].maxi;
        aint[nod].pmaxi = aint[2 * nod].pmaxi;


        if (aint[2 * nod].maxi2 >= aint[2 * nod + 1].maxi){
            aint[nod].maxi2 = aint[2 * nod].maxi2;
            aint[nod].pmaxi2 = aint[2 * nod].pmaxi2;
        }
        else {
            aint[nod].maxi2 = aint[2 * nod + 1].maxi;
            aint[nod].pmaxi2 = aint[2 * nod + 1].pmaxi;
        }

        if (aint[2 * nod + 1].maxi != aint[2 * nod].maxi){

            if (aint[2 * nod].altm >= aint[2 * nod + 1].maxi){
                aint[nod].altm = aint[2 * nod].altm;
                aint[nod].paltm = aint[2 * nod].paltm;
            }
            else {
                aint[nod].altm = aint[2 * nod + 1].maxi;
                aint[nod].paltm = aint[2 * nod + 1].pmaxi;
            }

        }
        else {
            if (aint[2 * nod].altm >= aint[2 * nod + 1].altm){
                aint[nod].altm = aint[2 * nod].altm;
                aint[nod].paltm = aint[2 * nod].paltm;
            }
            else {
                aint[nod].altm = aint[2 * nod + 1].altm;
                aint[nod].paltm = aint[2 * nod + 1].paltm;
            }
        }


    }
    else {
        aint[nod].maxi = aint[2 * nod + 1].maxi;
        aint[nod].pmaxi = aint[2 * nod + 1].pmaxi;
        aint[nod].maxi2 = aint[2 * nod + 1].maxi2;
        aint[nod].pmaxi2 = aint[2 * nod + 1].pmaxi2;

        if (aint[2 * nod].maxi != aint[2 * nod + 1].maxi){
            if (aint[2 * nod + 1].altm >= aint[2 * nod].maxi){
                aint[nod].altm = aint[2 * nod + 1].altm;
                aint[nod].paltm = aint[2 * nod + 1].paltm;
            }
            else {
                aint[nod].altm = aint[2 * nod].maxi;
                aint[nod].paltm = aint[2 * nod].pmaxi;
            }
        }
        else {
            if (aint[2 * nod + 1].altm >= aint[2 * nod].altm){
                aint[nod].altm = aint[2 * nod + 1].altm;
                aint[nod].paltm = aint[2 * nod + 1].paltm;
            }
            else {
                aint[nod].altm = aint[2 * nod].altm;
                aint[nod].paltm = aint[2 * nod].paltm;
            }
        }

    }

    /// sorted ins daca intervalul l .. r este crescator oricum
    if (aint[2 * nod].sorted && aint[2 * nod + 1].sorted && v[mid] <= v[mid + 1])
        aint[nod].sorted = 1;
    else aint[nod].sorted = 0;

}

int qsuff (int nod , int st , int dr , int l , int r){
    int mid = (st + dr) / 2 , sum = 0;

    if (l <= st && dr <= r){

        if (aint[nod].sorted)
            return st - dr + 1;

        sum = qsuff (2 * nod + 1 , mid + 1 , dr , l , r);

        if (sum == min(r , dr) - (mid + 1) + 1 && v[mid] <= v[mid + 1])
            sum += qsuff(2 * nod , st , mid , l , r);

        return sum;

    }

    if (mid + 1 <= r)
        sum = qsuff (2 * nod + 1 , mid + 1 , dr , l , r);

    if (l <= mid && (mid + 1 > r || (sum == min(r , dr) - (mid + 1) + 1 && v[mid] <= v[mid + 1])))
        sum += qsuff(2 * nod , st , mid , l , r);


    return sum;
}

int maxi , pmaxi , maxi2 , pmaxi2;


void qmaxi (int nod , int st , int dr , int l , int r){
    int mid = (st + dr) / 2;

    if (l <= st && dr <= r){

        if (maxi < aint[nod].maxi){
            maxi = aint[nod].maxi;
            pmaxi = aint[nod].pmaxi;
            maxi2 = aint[nod].maxi2;
            pmaxi2 = aint[nod].pmaxi2;
        }
        else if (maxi == aint[nod].maxi && maxi2 < aint[nod].altm){
            maxi2 = aint[nod].altm;
            pmaxi2 = aint[nod].paltm;
        }
        else if (maxi > aint[nod].maxi && maxi2 < aint[nod].maxi){
            maxi2 = aint[nod].maxi;
            pmaxi2 = aint[nod].pmaxi;
        }

        return;

    }

    if (l <= mid)
        qmaxi(2 * nod , st , mid , l , r);

    if (mid + 1 <= r)
        qmaxi (2 * nod + 1 , mid + 1 , dr , l , r);

}

int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , q , i , l , r , k , suff , a , b , st , dr , mid;
    fscanf (fin,"%d%d",&n,&q);
    for (i = 1 ; i <= n ; i++){
        fscanf (fin,"%d",&v[i]);
    }

    build (1 , 1 , n);

    for (;q;q--){
        fscanf (fin,"%d%d%d", &l , &r , &k);

        suff = qsuff (1 , 1 , n , l , r);
        r = r - suff;

        if (r < l){
            fprintf (fout,"1\n");
            continue;
        }

        /// acum intre l si r exista clar niste inversiuni

        maxi = -1;
        pmaxi = n + 1;

        maxi2 = -1;
        pmaxi2 = n + 1;

        qmaxi (1 , 1 , n , l , r);

        a = maxi;
        b = maxi2;


        st = r + 1;
        dr = r + suff; /// cauti cel mai mare element mai mic decat a

        while (st <= dr){
            mid = (st + dr) / 2;
            if ( a >= v[mid] )
                dr = mid - 1;
            else st = mid + 1;
        }

        if (st >= r + 1 && v[st] > b){
            b = v[st];
        }



        fprintf (fout,"%d\n", (a + b <= k) );

    }

    return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:173:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  173 |     fscanf (fin,"%d%d",&n,&q);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~
sortbooks.cpp:175:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  175 |         fscanf (fin,"%d",&v[i]);
      |         ~~~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:181:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  181 |         fscanf (fin,"%d%d%d", &l , &r , &k);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23