oj.uz

Submission #310765

# Submission time Handle Problem Language Result Execution time Memory
310765 2020-10-07T20:42:04 Z luciocf None (JOI16_matryoshka) C++14
0 / 100
 1022 ms 262148 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];
 
map<int, vector<int>> pos;
 
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 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Runtime error 1022 ms 262148 KB Execution killed with signal 9 (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 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Runtime error 1022 ms 262148 KB Execution killed with signal 9 (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 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Runtime error 1022 ms 262148 KB Execution killed with signal 9 (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 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Runtime error 1022 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -