oj.uz

Submission #888010

# Submission time Handle Problem Language Result Execution time Memory
888010 2023-12-15T18:59:28 Z BBart888 Exhibition (JOI19_ho_t2) C++14
0 / 100
 1 ms 2652 KB 
#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].second)
			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;
}



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

	for (int i = 1; i < MAXN; i++)
		dp[i] = { 1e18,0 };
	dp[0] = { 0,-1 };

	for (int i = 0; i < n; i++)
	{
		ll j = where_fit(0, n - 1, 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].second, idx));
	}

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


	


	

	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Incorrect 1 ms 2652 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Incorrect 1 ms 2652 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Incorrect 1 ms 2652 KB Output isn't correct
3 Halted 0 ms 0 KB -