Submission #218341

#	Time	Username	Problem	Language	Result	Execution time	Memory
218341		Lawliet	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1762 ms	101304 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) {}
};

class SegmentTree
{
	public:

		int getLeft(int node) { return 2*node; }
		int getRight(int node) { return 2*node + 1; }

		void update(int node, int l, int r, int i, int v)
		{
			if( i < l || r < i ) return;

			if( l == r )
			{
				mx[node] = max( mx[node] , v );
				return;
			}

			int m = ( l + r )/2;

			update( getLeft(node) , l , m , i , v );
			update( getRight(node) , m + 1 , r , i , v );

			mx[node] = max( mx[ getLeft(node) ] , mx[ getRight(node) ] );
		}

		int query(int node, int l, int r, int i, int j)
		{
			if( j < l || r < i ) return 0;
			if( i <= l && r <= j ) return mx[node];

			int m = ( l + r )/2;

			int maxLeft = query( getLeft(node) , l , m , i , j );
			int maxRight = query( getRight(node) , m + 1 , r , i , j );

			return max( maxLeft , maxRight );
		}

		SegmentTree() { memset( mx , 0 , sizeof(mx) ); }

	private:

		int mx[4*MAXN];
};

int n, q;

int v[MAXN];

bool ans[MAXN];

vector< int > s;

vector< query > sweep[MAXN];

SegmentTree SEG;

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

		if( s.back() != 0 )
		{
			int ind = s.back();
			SEG.update( 1 , 1 , n , ind , v[ind] + v[i] );
		}

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

			ans[curInd] = ( SEG.query( 1 , 1 , n , curL , i ) <= 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:76: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:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&v[i]);
   ~~~~~^~~~~~~~~~~~
sortbooks.cpp:87: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: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 23 / 23