Submission #329757

#	Time	Username	Problem	Language	Result	Execution time	Memory
329757		Rainbowbunny	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	2600 ms	262144 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;

int n, q;
int w[1000005], L[1000005], blocking[1000005];
int ST[1000005][20], up[1000005][20], val[1000005][20];

stack <pair <int, int> > S;

int Query(int l, int r)
{
	if(l > r)
	{
		return 0;
	}
	int temp = L[r - l + 1];
	return max(ST[l][temp], ST[r - (1 << temp) + 1][temp]);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> q;
	L[0] = -1;
	for(int i = 1; i <= n; i++)
	{
		L[i] = L[i >> 1] + 1;
		cin >> w[i];
		ST[i][0] = w[i];
	}
	for(int i = 1; i < 20; i++)
	{
		for(int j = 1; j + (1 << i) <= n + 1; j++)
		{
			ST[j][i] = max(ST[j][i - 1], ST[j + (1 << (i - 1))][i - 1]);
		}
	}
	for(int i = n; i >= 1; i--)
	{
		while(S.empty() == false && S.top().first < w[i])
		{
			S.pop();
		}
		if(S.empty())
		{
			up[i][0] = n + 1;
			if(Query(i + 1, n) == 0)
			{
				val[i][0] = 0;
			}
			else
			{
				val[i][0] = Query(i + 1, n) + w[i];
			}
		}
		else
		{
			up[i][0] = S.top().second;
			if(Query(i + 1, S.top().second - 1) == 0)
			{
				val[i][0] = 0;
			}
			else
			{
				val[i][0] = Query(i + 1, S.top().second - 1) + w[i];
			}
		}
		S.push(make_pair(w[i], i));
	}
	up[n + 1][0] = n + 1;
	val[n + 1][0] = 0;
	for(int i = 1; i < 20; i++)
	{
		up[n + 1][i] = n + 1;
		
		for(int j = n; j >= 1; j--)
		{
			up[j][i] = up[up[j][i - 1]][i - 1];
			val[j][i] = max(val[j][i - 1], val[up[j][i - 1]][i - 1]);
		}
	}
	while(q--)
	{
		int l, r, x;
		cin >> l >> r >> x;
		int tmp = 0;
		for(int i = 19; i >= 0; i--)
		{
			if(up[l][i] <= r)
			{
				tmp = max(tmp, val[l][i]);
				l = up[l][i];
			}
		}
		if(Query(l + 1, r) != 0)
		{
			tmp = max(tmp, Query(l + 1, r) + w[l]);
		}
		if(tmp > x)
		{
			cout << 0 << '\n';
		}
		else
		{
			cout << 1 << '\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