Submission #672094

#	Time	Username	Problem	Language	Result	Execution time	Memory
672094		GudStonks	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1196 ms	107332 KiB

sortbooks

#include<bits/stdc++.h>
using namespace std;
#define ft first
#define sd second
typedef long long ll;
const ll MOD = 1e9+7;
ll n, q, arr[1000005], brr[1000005], ans[1000005], t[(1000005 << 2)];
stack<ll>s;
vector<pair<pair<ll, ll>, pair<ll, ll> > >v;

void upd(ll pos, ll val, ll v = 1, ll tl = 1, ll tr = n){
	if(pos < tl || pos > tr)return;
	if(tl == tr){
		t[v] = max(t[v], val);
		return;
	}
	ll m = (tl + tr) / 2;
	upd(pos, val, v + v, tl, m);
	upd(pos, val, v + v + 1, m + 1, tr);
	t[v] = max(t[v + v], t[v + v + 1]);
}

ll get(ll l, ll r, ll v = 1, ll tl = 1, ll tr = n){
	if(r < tl || l > tr)return 0;
	if(l <= tl && tr <= r)
		return t[v];
	ll m = (tl + tr) / 2;
	return max(get(l, r, v + v, tl, m), get(l, r, v + v + 1, m + 1, tr));
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for(int i = 1; i <= n; i++){
		cin>>arr[i];
		while(!s.empty() && arr[s.top()] <= arr[i])s.pop();
		if(!s.empty())brr[i] = s.top();
		s.push(i);
	}
	for(int i = 1, a, b, c; i <= q; i++){
		cin>>a>>b>>c;
		v.push_back({{b, a}, {c, i}});
	}
	sort(v.begin(), v.end());
	ll j = 0;
	for(auto it : v){
		ll r = it.ft.ft, l = it.ft.sd, k = it.sd.ft, i = it.sd.sd;
		while(j < r){
			j++;
			if(brr[j]){
				upd(brr[j], arr[j] + arr[brr[j]]);
			}
		}
		ans[i] = (get(l, r) <= k ? 1 : 0);
	}
	for(int i = 1; i <= q; 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