Submission #235309

#	Time	Username	Problem	Language	Result	Execution time	Memory
235309		keta_tsimakuridze	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	1793 ms	131448 KiB

sortbooks

#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
long long n,m,k,a[1000006],cur,x[1000006],tree[4*1000006],i,ans[1000006];
vector<int>v[1000006];
pair< pair<int,int> , pair<int,int> > p[1000006];
void update(int u,int ind,int l,int r,int val){
	if(l>ind || r<ind) return;
	if(l==r) {
		tree[u]=val; return;
	}
	int mid=(l+r)/2;
	update(2*u,ind,l,mid,val);
	update(2*u+1,ind,mid+1,r,val);
	tree[u]=max(tree[2*u],tree[2*u+1]);
}
int getans(int u,int start,int end,int l,int r){
	if(l>end|| r<start) return 0;
	if(start<=l && r<=end) return tree[u];
	int mid=(l+r)/2;
	return max(getans(2*u,start,end,l,mid),getans(2*u+1,start,end,mid+1,r));
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(k=1;k<=n;k++){
		cin>>a[k];
		
		cur=k-1;
		while(a[cur]<=a[k] && cur!=0){
			cur=x[cur];
		}
		x[k]=cur;
		
		if(cur!=0) update(1,k,1,n,a[cur]+a[k]),
		v[cur].push_back(k);
	
	}
	
	for(k=1;k<=m;k++){
		cin>>p[k].f.f>>p[k].f.s>>p[k].s.f;
		p[k].s.s=k;
	}
	sort(p+1,p+m+1);
	i=1;
	for(k=1;k<=m;k++){
	
		while(i<p[k].f.f){
		
			for(int j=0;j<v[i].size();j++)
			update(1,v[i][j],1,n,0);
			
			i++;
		}
	
		if(getans(1,p[k].f.f,p[k].f.s,1,n)>p[k].s.f)ans[p[k].s.s]=0;
		else ans[p[k].s.s]=1;
	}
	for(k=1;k<=m;k++)
	cout<<ans[k]<<" ";
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:51:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<v[i].size();j++)
                ~^~~~~~~~~~~~

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