161842025-04-11 14:31:12lacitoNövekvő Ödön és a Másoló Varázslócpp17Elfogadva 100/100197ms5940 KiB
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	int n, m;
	cin >> n >> m;
	vector<int> A(n), B(m);
	for (int& a : A)
	{
		cin >> a;
	}
	for (int& b : B)
	{
		cin >> b;
	}
	sort(B.begin(), B.end());
	map<int, int> x;
	x[-n] = -n;
	x[0] = 0;
	int k2 = -1;
	int a;
	for (int i = 0; i < n; i++)
	{
		int k = lower_bound(B.begin(), B.end(), A[i]) - B.begin();
		int m = (k != k2 || A[i - 1] < A[i] ? prev(x.upper_bound(k - i))->second : a) + 1;
		k2 = k;
		auto it = x.upper_bound(k - i - 1);
		a = prev(it)->second;
		while (it != x.end() && it->second <= m)
			x.erase(it++);
		x[k - i - 1] = m;
	}
	cout << n - prev(x.upper_bound(m - n))->second;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Elfogadva37ms1588 KiB
subtask25/5
3Elfogadva50ms3128 KiB
4Elfogadva52ms3308 KiB
5Elfogadva50ms3124 KiB
subtask310/10
6Elfogadva1ms564 KiB
7Elfogadva1ms500 KiB
8Elfogadva1ms316 KiB
subtask415/15
9Elfogadva1ms316 KiB
10Elfogadva1ms500 KiB
11Elfogadva1ms428 KiB
12Elfogadva1ms316 KiB
subtask55/5
13Elfogadva3ms564 KiB
14Elfogadva3ms316 KiB
15Elfogadva4ms564 KiB
subtask65/5
16Elfogadva4ms316 KiB
17Elfogadva3ms756 KiB
18Elfogadva3ms564 KiB
19Elfogadva3ms316 KiB
subtask710/10
20Elfogadva4ms568 KiB
21Elfogadva4ms564 KiB
22Elfogadva4ms564 KiB
23Elfogadva3ms548 KiB
24Elfogadva4ms564 KiB
subtask825/25
25Elfogadva54ms3132 KiB
26Elfogadva54ms3124 KiB
27Elfogadva56ms3000 KiB
28Elfogadva1ms316 KiB
29Elfogadva93ms3124 KiB
30Elfogadva59ms3008 KiB
31Elfogadva59ms3124 KiB
32Elfogadva63ms2980 KiB
33Elfogadva65ms3008 KiB
34Elfogadva65ms3124 KiB
35Elfogadva68ms3084 KiB
36Elfogadva61ms3380 KiB
37Elfogadva61ms2996 KiB
38Elfogadva68ms3004 KiB
39Elfogadva94ms3124 KiB
40Elfogadva64ms3004 KiB
41Elfogadva70ms2992 KiB
42Elfogadva41ms2364 KiB
43Elfogadva61ms3124 KiB
44Elfogadva59ms3124 KiB
45Elfogadva64ms3132 KiB
subtask925/25
46Elfogadva123ms5836 KiB
47Elfogadva131ms5892 KiB
48Elfogadva119ms5832 KiB
49Elfogadva197ms5908 KiB
50Elfogadva196ms5684 KiB
51Elfogadva195ms5684 KiB
52Elfogadva120ms5940 KiB
53Elfogadva133ms5940 KiB
54Elfogadva135ms5684 KiB
55Elfogadva120ms5684 KiB