Submission #395794

#	Time	Username	Problem	Language	Result	Execution time	Memory
395794		CaroLinda	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	1519 ms	122208 KiB

sortbooks

#include <bits/stdc++.h>

#define ll long long
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define pb push_back
#define sz(x) (int)(x.size())

const int MAXN = 1e6+10 ;
const ll inf = 1e15+10 ;

using namespace std ;

struct Event
{
	bool type ; //0 is an object, 1 is a query
	ll weight ;
	int id ;

	Event(bool type = 0 , ll weight = 0 , int id =0 ) : 
	type(type) , weight(weight) , id(id) {}

	bool operator < ( Event other ) const
	{
		if(weight != other.weight) return weight > other.weight ;
		return type > other.type ;
	}

} ;

struct Seg
{
	int n ;
	int tree[MAXN*2] ;

	Seg() { for(int i= 0 ; i <MAXN*2 ; i++ ) tree[i] = -2 ; }

	void upd(int pos, int val) { for(pos += n ; pos > 0 ; pos >>= 1) tree[pos] = max(tree[pos] , val) ; }
	int qry(int l, int r)
	{
		int ans = -2 ;
		for(l += n , r += n ; l < r ; l >>= 1 , r >>= 1) 
		{
			if(l&1) ans = max(ans, tree[l++]) ;
			if(r&1) ans = max(ans, tree[--r]) ;
		}
		return ans ;
	}

} seg ;

int N , M ;
int lef[MAXN] , L[MAXN] , R[MAXN] ;
int ans[MAXN] ;
ll w[MAXN] , K[MAXN] ;
vector<Event> sweep ;

int main()
{	
	scanf("%d %d", &N, &M ) ;
	for(int i = 1 ; i <= N ; i++ ) scanf("%lld", &w[i] ) ;

	w[0] = inf;
	seg.n = N ;

	for(int i = 1 ;i <= N ; i++ )
	{
		lef[i] = i-1 ;
		while( w[lef[i]] <= w[i] ) lef[i] = lef[ lef[i] ] ;

		if(lef[i]) sweep.push_back( Event(0, w[lef[i]]+w[i] , i) ) ;
	}

	for(int i = 1 ; i <= M ; i++ )
	{
		scanf("%d %d %lld", &L[i], &R[i] , &K[i]) ;
		sweep.push_back( Event(1, K[i], i) ) ;
	}

	sort(all(sweep) );

	for(auto e : sweep )
	{		
		if(!e.type) seg.upd( e.id-1 , lef[e.id] ) ;
		else ans[e.id] = (seg.qry( L[e.id]-1 , R[e.id] ) < L[e.id]) ;
	}

	for(int i = 1 ; i <= M ; i++ ) printf("%d\n", ans[i]  ) ;

}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |  scanf("%d %d", &N, &M ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~
sortbooks.cpp:62:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   62 |  for(int i = 1 ; i <= N ; i++ ) scanf("%lld", &w[i] ) ;
      |                                 ~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   77 |   scanf("%d %d %lld", &L[i], &R[i] , &K[i]) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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