Submission #404321

#	Time	Username	Problem	Language	Result	Execution time	Memory
404321		Ruxandra985	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	1014 ms	63248 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 aib[DIMN] , n;
 
void update (int poz , int val){
 
    for (;poz <= n ; poz = (poz + (poz & (-poz))))
        aib[poz] = max(aib[poz] , val);
 
 
}
 
int query (int poz){
    int maxi = -1;
    for (;poz <= n ; poz = (poz + (poz & (-poz))))
        maxi = max(maxi , aib[poz]);
 
    return maxi;
 
 
}
 
 
 
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int 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(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(l) <= 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:62: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]
   62 |         for (j = 0 ; j < q[i].size() ; j++){
      |                      ~~^~~~~~~~~~~~~
sortbooks.cpp:34:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     fscanf (fin,"%d%d",&n,&qr);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
sortbooks.cpp:37:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         fscanf (fin,"%d",&v[i]);
      |         ~~~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:49:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         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