Submission #310763

#	Time	Username	Problem	Language	Result	Execution time	Memory
310763		luciocf	Matryoshka (JOI16_matryoshka)	C++14	100 / 100	813 ms	50168 KiB

matryoshka

#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

typedef pair<int, int> pii;

const int maxn = 4e5+10;

struct SegmentTree
{
	int tree[3*maxn];

	void upd(int node, int l, int r, int pos, int v)
	{
		if (l == r)
		{
			tree[node] = v;
			return;
		}

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

		if (pos <= mid) upd(2*node, l, mid, pos, v);
		else upd(2*node+1, mid+1, r, pos, v);

		tree[node] = max(tree[2*node], tree[2*node+1]);
	}

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

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

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

struct Query
{
	int r, h, ind;
} qry[maxn];

int n, q;
pii a[maxn];

int ans[maxn];

vector<int> pos[maxn];

void compress(void)
{
	map<int, int> mp;

	for (int i = 1; i <= n; i++)
		mp[a[i].ss] = 0;
	for (int i = 1; i <= q; i++)
		mp[qry[i].h] = 0;

	int aux = 0;
	for (auto &x: mp)
		x.second = ++aux;

	for (int i = n; i >= 1; i--)
	{
		a[i].ss = mp[a[i].ss];
		pos[a[i].ss].push_back(i);
	}

	for (int i = 1; i <= q; i++)
		qry[i].h = mp[qry[i].h];
}

bool comp(pii x, pii y)
{
	if (x.ff == y.ff) return x.ss > y.ss;
	return x.ff < y.ff;
}

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

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

	for (int i = 1; i <= q; i++)
	{
		scanf("%d %d", &qry[i].r, &qry[i].h);
		qry[i].ind = i;
	}

	sort(a+1, a+n+1, comp);
	sort(qry+1, qry+q+1, [&] (Query a, Query b) {return a.h < b.h;});

	compress();

	int ptr = 1;

	for (int i = 1; i <= q; i++)
	{
		while (ptr <= qry[i].h)
		{
			for (auto j: pos[ptr])
			{
				int mx = seg.query(1, 1, n, j+1, n)+1;
				seg.upd(1, 1, n, j, mx);
			}

			ptr++;
		}

		int pos = (int)(lower_bound(a+1, a+n+1, make_pair(qry[i].r, 0))-a);

		ans[qry[i].ind] = seg.query(1, 1, n, pos, n);
	}

	for (int i = 1; i <= q; i++)
		printf("%d\n", ans[i]);
}

Compilation message (stderr)

matryoshka.cpp: In function 'int main()':
matryoshka.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   86 |  scanf("%d %d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~
matryoshka.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   89 |   scanf("%d %d", &a[i].ff, &a[i].ss);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
matryoshka.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   93 |   scanf("%d %d", &qry[i].r, &qry[i].h);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 49 / 49