Submission #503235

#	Time	Username	Problem	Language	Result	Execution time	Memory
503235		mosiashvililuka	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	946 ms	94416 KiB

sortbooks

#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,f[1000009],K,tes,t,l,r,ans[1000009],F[1000009],fen[1000009];
pair <pair <int, int>, int> p[1000009];
vector <int> v[1000009];
stack <int> st;
void upd(int q, int w){
	q=a+2-q;
	while(q<=1000003){
		fen[q]=max(fen[q],w);
		q=q+(q&(-q));
	}
}
int read(int q){
	q=a+2-q;
	int sm=0;
	while(q>0){
		sm=max(sm,fen[q]);
		q=q-(q&(-q));
	}
	return sm;
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a>>tes;
	for(i=1; i<=a; i++) cin>>f[i];
	for(t=1; t<=tes; t++){
		cin>>p[t].first.first>>p[t].first.second>>p[t].second;
		v[p[t].first.second].push_back(t);
	}
	for(i=1; i<=a; i++){
		while(st.size()&&f[st.top()]<=f[i]) st.pop();
		if(st.size()){
			F[i]=st.top();
		}
		st.push(i);
	}
	for(i=1; i<=a; i++){
		if(F[i]!=0){
			upd(F[i],f[i]+f[F[i]]);
		}
		for(vector <int>::iterator it=v[i].begin(); it!=v[i].end(); it++){
			zx=read(p[(*it)].first.first);
			if(zx<=p[(*it)].second){
				ans[(*it)]=1;
			}else{
				ans[(*it)]=0;
			}
		}
	}
	for(t=1; t<=tes; t++){
		cout<<ans[t]<<"\n";
	}
	return 0;
}

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