oj.uz

Submission #310764

# Submission time Handle Problem Language Result Execution time Memory
310764 2020-10-07T20:41:00 Z luciocf None (JOI16_matryoshka) C++14
0 / 100
 10 ms 9984 KB 
#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

typedef pair<int, int> pii;

const int maxn = 2e5+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];

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

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

	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

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

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Runtime error 10 ms 9984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Runtime error 10 ms 9984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Runtime error 10 ms 9984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4992 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Runtime error 10 ms 9984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -