Submission #888022

#	Time	Username	Problem	Language	Result	Execution time	Memory
888022		BBart888	Exhibition (JOI19_ho_t2)	C++14	0 / 100	1 ms	2656 KiB

joi2019_ho_t2

#include <cstdio>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <queue>
#include <stack>
#include <cassert>
#include <cstring>
#include <climits>
#include <functional>
#include<cstdlib>
//#include "arc.h"
//#include "dreaming.h"



using namespace std;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long LL;



const int MAXN = 1e5 + 11; 
using ll = long long;
const ll mod1 = 1e9 + 7;
const ll mod2 = 1000000021;
const ll P = 31;



void setIO(string name = "") {
	cin.tie(0)->sync_with_stdio(0); // see /general/fast-io
	if ((name.size())) {
		//freopen((name + ".in").c_str(), "r", stdin); // see /general/input-output
		//freopen((name + ".out").c_str(), "w", stdout);
	}
}



int n, m;
pair<ll, ll> paintings[MAXN];
ll frames[MAXN];
pair<ll, ll> dp[MAXN];

int where_fit(int l, int r,int id)
{
	while (l < r)
	{
		int m = (l + r) / 2;
		if (dp[m].first > paintings[id].first)
			r = m;
		else
			l = m + 1;
	}
	return l;
}

int smallest_good(int l, int r, int id)
{
	while (l < r)
	{
		int m = (l + r) / 2;
		if (frames[m] >= paintings[id].first)
			r = m;
		else
			l = m + 1;
	}
	return l;
}


bool cmp(pair<ll, ll> a, pair<ll, ll> b)
{
	if (a.second == b.second)
		return a.first < b.first;
	return a.second < b.second;
}


int main()
{
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(false);
	//setIO("radio");
	
	
	cin >> n >> m;

	for (int i = 0; i < n; i++)
		cin >> paintings[i].first >> paintings[i].second;

	for (int i = 0; i < m; i++)
		cin >> frames[i];

	sort(frames, frames + m);

	sort(paintings, paintings + n,cmp);

	for (int i = 1; i < MAXN; i++)
		dp[i] = { 1e18,0 };
	dp[0] = { 0,-1 };
	frames[m] = 1e18;
	for (int i = 0; i < n; i++)
	{
		ll j = where_fit(0, 2*n, i);
		ll L = dp[j - 1].second + 1;
		ll idx = smallest_good(L, m, i);
		//cout << i << " : " << L << " = " << idx << '\n';
		if(idx < m)
			dp[j] = min(dp[j], make_pair(paintings[i].first, idx));
	}


	for (int i = 0; i < MAXN; i++)
	{
		if (dp[i].first == 1e18)
		{
			cout << i - 1 << '\n';
			break;
		}
	}


	


	

	return 0;
}

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