Submission #831671

#	Time	Username	Problem	Language	Result	Execution time	Memory
831671		OAleksa	Exhibition (JOI19_ho_t2)	C++14	0 / 100	1 ms	340 KiB

joi2019_ho_t2

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std; 
#define int long long
const int maxn = 1e5 + 69;
const int inf = 1e9 + 69;
int n, m, c[maxn], st[4 * maxn];
pair<int, int> a[maxn];
void build(int v, int tl, int tr) {
	if(tl == tr)
		st[v] = a[tl].s;
	else {
		int mid = (tl + tr) / 2;
		build(v * 2 + 1, tl, mid);
		build(v * 2 + 2, mid + 1, tr);
		st[v] = min(st[v * 2 + 1], st[v * 2 + 2]);
	}
}

void upd(int v, int tl, int tr, int x) {
	if(tl == tr) 
		st[v] = inf;
	else {
		int mid = (tl + tr) / 2;
		if(st[v * 2 + 1] == x)
			upd(v * 2 + 1, tl, mid, x);
		else
			upd(v * 2 + 2, mid + 1, tr, x);
		st[v] = min(st[v * 2 + 1], st[v * 2 + 2]);
	}
}

int qry(int v, int tl, int tr, int l, int r) {
	if(tl > r || tr < l)
		return inf;
	else if(tl >= l && tr <= r)
		return st[v];
	else {
		int mid = (tl + tr) / 2;
		return min(qry(v * 2 + 1, tl, mid, l, r), qry(v * 2 + 2, mid + 1, tr, l, r));
	}
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int tt = 1;
	//cin >> tt;
	while(tt--) {
		cin >> n >> m;
		for(int i = 0;i < n;i++) 
			cin >> a[i].f >> a[i].s;
		for(int i = 0;i < m;i++)
			cin >> c[i];
		sort(c, c + m);
		sort(a, a + n);
		auto check = [&](int mid) {
			build(0, 0, n - 1);
			int r = 0, p = 0;
			for(int i = m - mid;i < m;i++) {
				pair<int, int> x = {c[i], inf};
				auto u = upper_bound(a, a + n, x) - a;
				if(u != 0) {
					--u;
					int pr = qry(0, 0, n - 1, 0, u);
					if(pr >= p && pr != inf) {
						++r;
						upd(0, 0, n - 1, pr);
						p = pr;
					}
				}
			}
			return r >= mid;
		};
		int l = 1, r = m, ans = 0;
		while(l <= r) {
			int mid = (l + r) / 2;
			if(check(mid)) {
				ans = mid;
				l = mid + 1;
			}
			else
				r = mid - 1;
		}
		cout << ans << endl;
	}
   return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 50