Submission #202075

#	Time	Username	Problem	Language	Result	Execution time	Memory
202075		guangxuan	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	2272 ms	183560 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
int a[1000009];
vector<pair<int,pair<int,int> > > qs[1000009]; // end, k, qi
bool ans[1000009];
int lg[1000009];

struct node{
	int s,e,m,v;
	node *l,*r;
	node(int _s,int _e):s(_s),e(_e),m((_s+_e)/2),v(0){
		if(s==e)return;
		l = new node(s,m);
		r = new node(m+1,e);
	}
	int qu(int x,int y){
		if(s==x&&e==y)return v;
		if(x>m)return r->qu(x,y);
		if(y<=m)return l->qu(x,y);
		return max(l->qu(x,m),r->qu(m+1,y));
	}
	void up(int x,int uv){
		if(s==e){v= max(v,uv);return;}
		if(x>m)r->up(x,uv);
		else l->up(x,uv);
		v = max(l->v,r->v);
	}
}*root;

int main(){
	int n,t;
	scanf("%d%d",&n,&t);
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	for(int ti=0;ti<t;ti++){
		int l,r,k;
		scanf("%d%d%d",&l,&r,&k);
		qs[r-1].push_back({l-1,{k,ti}});
	}
	stack<int> stk;
	for(int i=0;i<n;i++){
		while(stk.size()&&a[stk.top()]<=a[i])stk.pop();
		if(stk.size()==0)lg[i]=-1;
		else lg[i]=stk.top();
		stk.push(i);
	}
	root = new node(0,n-1);
	for(int r=0;r<n;r++){
		if(lg[r]!=-1){
			int lgr = lg[r];
			root->up(lgr,a[lgr]+a[r]);
		}
		for(auto q:qs[r]){
			int maxsum = root->qu(q.first,r);
			if(q.second.first>=maxsum)ans[q.second.second]=1;
			//printf("MS%d K%d\n",maxsum,q.second.first);
		}
	}
	for(int i=0;i<t;i++){
		printf("%d\n",ans[i]);
	}
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&t);
  ~~~~~^~~~~~~~~~~~~~
sortbooks.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
   ~~~~~^~~~~~~~~~~~
sortbooks.cpp:38: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