Submission #1092990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092990		Nurislam	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1028 ms	149080 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long


template <class F, class _S>
bool chmin(F &u, const _S &v){
	bool flag = false;
	if ( u > v ){
		u = v; flag |= true;
	}
	return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
	bool flag = false;
	if ( u < v ){
		u = v; flag |= true;
	}
	return flag;
}

const int N = 1e6+50, inf = 1e18+200;
//int mod = 998244353;
//int mod = 1000000007;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#define rnd(l, r) uniform_int_distribution <int> (l, r)(rng)

struct segtree{
	vector<int> t;
	segtree(){
		t.resize(N*4);
	};
	void upd(int ps, int vl, int i = 1, int l = 1, int r = N){
		if(l == r){
			t[i] = vl;
			return;
		}
		int m = (l+r)>>1;
		if(ps <= m)upd(ps, vl, i*2, l, m);
		else upd(ps, vl, i*2+1, m+1, r);
		t[i] = max(t[i*2], t[i*2+1]);
	};
	int get(int tl, int tr, int i = 1, int l = 1, int r = N){
		if(l > tr || r < tl)return 0;
		if(tl <= l && r <= tr)return t[i];
		int m = (l+r)>>1;
		return max(	get(tl, tr, i*2, l, m), get(tl, tr, i*2+1, m+1, r));
	};
}t;

void solve(){
	
	
	int n, m;
	cin >> n >> m;
	vector<int> a(n+1, 0);
	for(int i = 1; i <= n; i++)cin >> a[i];
	vector<array<int,3>> q(m);
	for(auto &[l, r, k]:q)cin >> l >> r >> k;
	vector<vector<int>> g(n+1);
	for(int i = 0; i < m; i++){
		auto [l,r,k] = q[i];
		g[r].pb(i);
	}
	vector<int> ans(m);
	stack<int> st;
	for(int i = 1; i <= n; i++){
		while(st.size() && a[st.top()] <= a[i])st.pop();
		if(st.size()){
			t.upd(st.top(), a[st.top()]+a[i]);
		}
		for(auto id:g[i]){
			auto [l, r, k] = q[id];
			//cout << t.get(l, r) << '\n';
			ans[id] = t.get(l, r) <= k;
		}
		st.push(i);
	}
	for(auto i:ans)cout << i << '\n';
}

 
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int tt = 1;
	//cin >> tt;
	while(tt--){
		solve();
	}
}
 
 
 
 
 
 
 
 
 
 
 
 
 

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