Submission #347935

#	Time	Username	Problem	Language	Result	Execution time	Memory
347935		luciocf	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	888 ms	262148 KiB

sortbooks

#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

typedef pair<int, int> pii;

const int maxn = 1e6+10;
const int inf = 1e9+10;

int n;
int a[maxn];

struct MergeSortTree
{
	vector<int> lista[4*maxn];
	pii tree[4*maxn];

	void join(int node, int l, int r)
	{
		lista[node].resize(r-l+1);
		
		int L = 2*node, R = 2*node+1;
		merge(lista[L].begin(), lista[L].end(), lista[R].begin(), lista[R].end(), back_inserter(lista[node]));

		tree[node].ff = max(tree[2*node].ff, tree[2*node+1].ff);
		tree[node].ss = max(tree[2*node].ss, tree[2*node+1].ss);

		int mx = tree[2*node].ss;
		auto it = lower_bound(lista[2*node+1].begin(), lista[2*node+1].end(), mx);

		if (it != lista[2*node+1].begin())
		{
			--it;
			tree[node].ff = max(tree[node].ff, mx + *it);
		}
	}

	void build(int node, int l, int r)
	{
		if (l == r)
		{
			lista[node].push_back(a[l]);
			tree[node] = {0, a[l]};
			return;
		}

		int mid = (l+r)>>1;

		build(2*node, l, mid); build(2*node+1, mid+1, r);

		join(node, l, r);
	}

	int getmax(int node, int l, int r, int a, int b)
	{
		if (l > b || r < a) return -inf;
		if (l >= a && r <= b) return tree[node].ss;
 
		int mid = (l+r)>>1;
 
		return max(getmax(2*node, l, mid, a, b), getmax(2*node+1, mid+1, r, a, b)); 
	}

	int query(int node, int l, int r, int a, int b)
	{
		if (l > b || r < a) return 0;
		if (l >= a && r <= b)
		{
			int ans = tree[node].ff;

			if (l != a)
			{
				int mx = getmax(1, 1, n, a, l-1);
				auto it = lower_bound(lista[node].begin(), lista[node].end(), mx);

				if (it != lista[node].begin())
				{
					--it;
					ans = max(ans, mx + *it);
				}
			}

			return ans;
		}

		int mid = (l+r)>>1;

		return max(query(2*node, l, mid, a, b), query(2*node+1, mid+1, r, a, b)); 
	}
} seg;

int main(void)
{
	int m;
	scanf("%d %d", &n, &m);

	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);

	seg.build(1, 1, n);

	while (m--)
	{
		int l, r, k;
		scanf("%d %d %d", &l, &r, &k);

		if (seg.query(1, 1, n, l, r) > k) printf("0\n");
		else printf("1\n");
	}
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   98 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
sortbooks.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  101 |   scanf("%d", &a[i]);
      |   ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:108:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  108 |   scanf("%d %d %d", &l, &r, &k);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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