Submission #404323

#	Time	Username	Problem	Language	Result	Execution time	Memory
404323		Ruxandra985	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	1746 ms	100488 KiB

sortbooks

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

int v[DIMN] , bigger[DIMN] , st[DIMN] , sol[DIMN];
vector <pair <int , pair <int , int> > > q[DIMN];

int aint[4 * DIMN];


void update (int nod , int st , int dr , int poz , int sum){
    int mid = (st + dr)/2;

    if (st == dr){
        aint[nod] = max(aint[nod] , sum);
        return;
    }

    if (poz <= mid)
        update (2 * nod , st , mid , poz , sum);
    else update (2 * nod + 1 , mid + 1 , dr , poz , sum);

    aint[nod] = max(aint[2 * nod] , aint[2 * nod + 1]);

}

int query (int nod , int st , int dr , int l , int r){
    int mid = (st + dr) / 2 , maxi = -1;

    if (l <= st && dr <= r){
        return aint[nod];
    }

    if (l <= mid)
        maxi = max(maxi , query(2 * nod , st , mid , l , r));

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

    return maxi;
}

int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , qr , i , l , r , k , elem , j , idx;
    fscanf (fin,"%d%d",&n,&qr);
    elem = 0;
    for (i = 1 ; i <= n ; i++){
        fscanf (fin,"%d",&v[i]);
        while (elem && v[st[elem]] <= v[i])
            elem--;

        bigger[i] = st[elem];
        st[++elem] = i;

    }

    /// bigger[i] = primul > v[i] de la stanga lui i

    for (i = 1 ; i <= qr ; i++){
        fscanf (fin,"%d%d%d", &l , &r , &k);

        q[r].push_back(make_pair(l , make_pair(k , i)));

    }


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

        /// adaugi i ul pt evaluat
        if (bigger[i])
            update(1 , 1 , n , bigger[i] , v[i] + v[bigger[i]]);

        for (j = 0 ; j < q[i].size() ; j++){

            r = i;
            l = q[i][j].first;
            k = q[i][j].second.first;
            idx = q[i][j].second.second;

            /// query de la l in colo, suma maxima

            sol[idx] = (query(1 , 1 , n , l , r) <= k);

        }

    }


    for (i = 1 ; i <= qr ; i++){
        fprintf (fout,"%d\n",sol[i]);
    }

    return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:76:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for (j = 0 ; j < q[i].size() ; j++){
      |                      ~~^~~~~~~~~~~~~
sortbooks.cpp:48:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     fscanf (fin,"%d%d",&n,&qr);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
sortbooks.cpp:51:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         fscanf (fin,"%d",&v[i]);
      |         ~~~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:63:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         fscanf (fin,"%d%d%d", &l , &r , &k);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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