Submission #383419

#	Time	Username	Problem	Language	Result	Execution time	Memory
383419		MODDI	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	3094 ms	68616 KiB

sortbooks

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define mp make_pair
#define pb push_back
using namespace std;
int n, q;
vi arr;
class pt{
	public:
		int sm;
		int mx;
		ll mood;
};
vector<pt> tree(4 * 1000000);
ll max(ll a, ll b){
	if(a > b)
		return a;
	return b;
}
void build(int node, int l, int r){
	if(l == r){
		pt cur;
		cur.mood = 0;
		cur.mx = arr[l];
		cur.sm = arr[l];
		tree[node] = cur;
	}
	else{
		int mid = (l + r) / 2;
		build(node * 2, l, mid);
		build(node * 2 + 1, mid + 1, r);
		pt next;
		next.sm = min(tree[node * 2].sm, tree[node * 2 + 1].sm);
		next.mx = max(tree[node * 2].mx, tree[node * 2 + 1].mx);
		next.mood = 0;
		if(tree[node * 2 + 1].sm < tree[node * 2].mx)
			next.mood = tree[node * 2 + 1].sm + tree[node * 2].mx;
		if(tree[node * 2].mx > tree[node * 2 + 1].mx)
		next.mood = max(next.mood,tree[node * 2 + 1].mx + tree[node * 2].mx);
		next.mood = max(next.mood, tree[node * 2].mood);
		next.mood = max(next.mood, tree[node * 2 + 1].mood);
	//	cout<<l<<" "<<r<<" with mood"<<next.mood<<endl;
		tree[node] = next;
	}
}
pt query(int node, int l, int r, int  L, int R){
	if(r < L || l > R){
		pt ret;
		ret.sm = 1e9;
		ret.mx = 0;
		ret.mood = 0;
		return ret;
	}
	if(L <= l && r <= R)	return tree[node];
	
	int mid = (l + r) / 2;
	pt left = query(node * 2, l, mid, L, R);
	pt right = query(node * 2 + 1, mid + 1, r, L, R);
	pt next;
	next.sm = min(left.sm, right.sm);
	next.mx = max(left.mx, right.mx);
	next.mood = 0;
	if(left.mx > right.sm)
		next.mood = right.sm + left.mx;
	if(left.mx > right.mx)
		next.mood = max(next.mood, left.mx + right.mx);
	next.mood = max(next.mood, left.mood);
	next.mood = max(next.mood, right.mood);
	return next;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	for(int i = 0; i < n; i++){
		int a;
		cin>>a;
		arr.pb(a);
	}
	build(1, 0, n -1);
	while(q--){
		int a, b, k;
		cin>>a>>b>>k;
		a--; b--;
		pt rn = query(1, 0, n - 1, a, b);
		//cout<<rn.mood<<endl;
		if(k >= rn.mood)
			cout<<1<<endl;
		else
			cout<<0<<endl;
			
	}
	return 0;
}

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