Submission #1277347

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277347		WH8	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	1940 ms	182904 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define ld long double

struct node {
	int s, e, m, v;
	node *l, *r;
	node (int S, int E){
		s=S,e=E,m=(e+s)/2,v=0;
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	void upd(int x, int nv){
		if(s==e){
			assert(s==x);
			v=nv;
			return;
		}
		if(x<=m)l->upd(x,nv);
		else r->upd(x, nv);
		v=max(l->v,r->v);
	}
	int qry(int S, int E){
		if(S<=s and e<=E){
			return v;
		}
		if(E<=m)return l->qry(S,E);
		else if(S>m)return r->qry(S,E);
		return max(l->qry(S,m), r->qry(m+1,E));
	}
} *root;

signed main(){
	int n,m;cin>>n>>m;
	int w[n+1];for(int i=1;i<=n;i++){cin>>w[i];}
	int ans[m];
	vector<tuple<int,int,int,int>> qs;
	for(int i=0;i<m;i++){
		int a,b,c;cin>>a>>b>>c;
		qs.pb({a,b,c,i});
	}
	sort(qs.begin(),qs.end());
	reverse(qs.begin(),qs.end());
	int qp=0;
	root=new node(1, n);
	stack<int> s;
	for(int i=n-1;i>=0;i--){
		while(!s.empty() and w[s.top()] < w[i]){
			root->upd(s.top(), w[s.top()]+w[i]);
			s.pop();
		}
		s.push(i);
		while(qp < m and get<0>(qs[qp])>=i){
			auto [l, r, k, ind] = qs[qp];
			if(root->qry(l, r) > k)ans[ind]=0;
			else ans[ind]=1;
			qp++;
		}
	}
	for(int i=0;i<m;i++){
		cout<<ans[i]<<"\n";
	}
}

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