Submission #347937

#	Time	Username	Problem	Language	Result	Execution time	Memory
347937		luciocf	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	34 / 100	3087 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 Node
{
	Node *l, *r;
	int v;
} *version[maxn];

struct PersistentSegmentTree
{
	int val(Node *node) {return node ? node->v : 0;}

	void upd(Node *prev, Node *node, int l, int r, int pos)
	{
		if (l == r)
		{
			node->v = (prev ? prev->v : 0) + 1;
			return;
		}

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

		if (pos <= mid)
		{
			node->l = new Node();
			if (prev) node->r = prev->r;

			upd((prev ? prev->l : NULL), node->l, l, mid, pos);
		}
		else
		{
			node->r = new Node();
			if (prev) node->l = prev->l;

			upd((prev ? prev->r : NULL), node->r, mid+1, r, pos);
		}

		node->v = val(node->l) + val(node->r);
	}

	int get(Node *prev, Node *node, int l, int r, int v)
	{
		if (!node || l >= v || val(node) == val(prev)) return -inf;
		if (l == r) return l;

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

		int p1 = get((prev ? prev->r : NULL), node->r, mid+1, r, v);

		if (p1 == -inf) return get((prev ? prev->l : NULL), node->l, l, mid, v);
		return p1;
	}
} pseg;

struct SegmentTree
{
	pii tree[4*maxn];

	void join(int node, int l, int r)
	{
		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 mid = (l+r)>>1;

		int mx = tree[2*node].ss;
		int v = pseg.get(version[mid], version[r], 0, inf, mx);

		tree[node].ff = max(tree[node].ff, mx + v);
	}

	void build(int node, int l, int r)
	{
		if (l == r)
		{
			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);
				int v = pseg.get(version[l-1], version[r], 0, inf, mx);

				ans = max(ans, mx + v);
			}

			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]);

	version[0] = new Node();
	for (int i = 1; i <= n; i++)
	{
		version[i] = new Node();
		pseg.upd(version[i-1], version[i], 0, inf, 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:137:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  137 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
sortbooks.cpp:140:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  140 |   scanf("%d", &a[i]);
      |   ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:154:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  154 |   scanf("%d %d %d", &l, &r, &k);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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