Submission #402690

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

sortbooks

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

struct segm{

    int maxi , pmaxi , sorted;

} 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].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;
    }
    else {
        aint[nod].maxi = aint[2 * nod + 1].maxi;
        aint[nod].pmaxi = aint[2 * nod + 1].pmaxi;
    }

    /// 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 == r - (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 && sum == r - (mid + 1) + 1 && v[mid] <= v[mid + 1])
        sum += qsuff(2 * nod , st , mid , l , r);


    return sum;
}

int maxi , pmaxi;


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

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

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

        a = maxi;

        l = pmaxi + 1;
        r += suff;

        maxi = 0;
        pmaxi = n + 1;
        qmaxi (1 , 1 , n , l , r);

        b = maxi;

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

    }

    return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:99:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |     fscanf (fin,"%d%d",&n,&q);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~
sortbooks.cpp:101:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         fscanf (fin,"%d",&v[i]);
      |         ~~~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:107:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         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