Submission #500525

#	Time	Username	Problem	Language	Result	Execution time	Memory
500525		sireanu_vlad	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	2484 ms	97548 KiB

sortbooks

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int n, m, w[1000001], a[5000001], l[1000001], pos, val, x, y;
bool f[1000001];

struct Query { int id, l, k; };
vector<Query> q[1000001];

stack<int> s;

void update(int nod, int l, int r)
{
	if(l == r) a[nod] = max(a[nod], val);
	else
	{
		int m = (l + r)/2;
		if(pos <= m) update(2*nod, l, m);
		else update(2*nod+1, m+1, r);
		a[nod] = max(a[2*nod], a[2*nod+1]);
	}
}

void read()
{
	cin >> n >> m;
	for(int i = 1; i <= n; ++i)
		cin >> w[i];
	for(int i = 1, r, l, k; i <= m; ++i)
	{
		cin >> l >> r >> k;
		q[r].push_back({i, l, k});
	}
}

int query(int nod, int l, int r)
{
	if(x <= l && r <= y) return a[nod];
	int m = (l + r)/2, rez = 0;
	if(x <= m) rez = max(rez, query(2*nod, l, m));
	if(m < y) rez = max(rez, query(2*nod+1, m+1, r));
	return rez;
}

void config()
{
	for(int i = 1; i <= n; ++i)
	{
		l[i] = i;
		for(;!s.empty() && w[i] >= w[s.top()];s.pop())
			l[i] = l[s.top()];
		s.push(i);
	}
}

void afis()
{
	for(int i = 1; i <= m; ++i)
		cout << f[i] << '\n';
}

void solve()
{
	for(int i = 1; i <= n; ++i)
	{
		if(l[i] > 1)
		{
			pos = l[i] - 1;
			val = w[i] + w[pos];
			update(1, 1, n);
		}
		for(auto j : q[i])
		{
			x = j.l, y = i;
			f[j.id] = (j.k >= query(1, 1, n));
		}
	}
}

int main()
{
	read();
	config();
	solve();
	afis();
	return 0;
}

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