Submission #218339

#	Time	Username	Problem	Language	Result	Execution time	Memory
218339		Lawliet	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	1078 ms	52604 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1000010;
const int INF = 1000000010;

struct query
{
	int L, k;
	int ind;

	query(int l, int k, int i)
		: L(l), k(k), ind(i) {}
};

int n, q;

int v[MAXN];

bool ans[MAXN];

vector< int > s;

vector< query > sweep[MAXN];

int main()
{
	scanf("%d %d",&n,&q);

	v[0] = INF;
	s.push_back( 0 );

	for(int i = 1 ; i <= n ; i++)
		scanf("%d",&v[i]);

	for(int i = 1 ; i <= q ; i++)
	{
		int L, R, k;
		scanf("%d %d %d",&L,&R,&k);

		sweep[R].push_back( query( L , k , i ) );
	}

	for(int i = 1 ; i <= n ; i++)
	{
		while( v[ s.back() ] <= v[i] )
			s.pop_back();

		s.push_back( i );

		while( !sweep[i].empty() )
		{
			int curL = sweep[i].back().L;
			int curK = sweep[i].back().k;
			int curInd = sweep[i].back().ind;
			sweep[i].pop_back();

			int aux = lower_bound( s.begin() , s.end() , curL ) - s.begin();

			if( aux == s.size() - 1 ) ans[curInd] = true;
			else
			{
				int A = v[ s[aux] ];
				int B = v[ s[aux + 1] ];

				ans[curInd] = ( A + B <= curK );
			}
		}
	}

	for(int i = 1 ; i <= q ; i++)
	{
		if( ans[i] ) printf("1\n");
		else printf("0\n");
	}
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:61:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if( aux == s.size() - 1 ) ans[curInd] = true;
        ~~~~^~~~~~~~~~~~~~~
sortbooks.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&q);
  ~~~~~^~~~~~~~~~~~~~~
sortbooks.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&v[i]);
   ~~~~~^~~~~~~~~~~~
sortbooks.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%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