제출 #404319

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
404319		Ruxandra985	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	1035 ms	68876 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 ; 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;
}

컴파일 시 표준 에러 (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