Submission #16,184

2025-04-11 14:31:12

cpp17

Accepted 100/100

197ms

5940 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;
}

	Sum	Test	Verdict	Time	Memory
subtask1	0/0
		1	Accepted	1ms	316 KiB
		2	Accepted	37ms	1588 KiB
subtask2	5/5
		3	Accepted	50ms	3128 KiB
		4	Accepted	52ms	3308 KiB
		5	Accepted	50ms	3124 KiB
subtask3	10/10
		6	Accepted	1ms	564 KiB
		7	Accepted	1ms	500 KiB
		8	Accepted	1ms	316 KiB
subtask4	15/15
		9	Accepted	1ms	316 KiB
		10	Accepted	1ms	500 KiB
		11	Accepted	1ms	428 KiB
		12	Accepted	1ms	316 KiB
subtask5	5/5
		13	Accepted	3ms	564 KiB
		14	Accepted	3ms	316 KiB
		15	Accepted	4ms	564 KiB
subtask6	5/5
		16	Accepted	4ms	316 KiB
		17	Accepted	3ms	756 KiB
		18	Accepted	3ms	564 KiB
		19	Accepted	3ms	316 KiB
subtask7	10/10
		20	Accepted	4ms	568 KiB
		21	Accepted	4ms	564 KiB
		22	Accepted	4ms	564 KiB
		23	Accepted	3ms	548 KiB
		24	Accepted	4ms	564 KiB
subtask8	25/25
		25	Accepted	54ms	3132 KiB
		26	Accepted	54ms	3124 KiB
		27	Accepted	56ms	3000 KiB
		28	Accepted	1ms	316 KiB
		29	Accepted	93ms	3124 KiB
		30	Accepted	59ms	3008 KiB
		31	Accepted	59ms	3124 KiB
		32	Accepted	63ms	2980 KiB
		33	Accepted	65ms	3008 KiB
		34	Accepted	65ms	3124 KiB
		35	Accepted	68ms	3084 KiB
		36	Accepted	61ms	3380 KiB
		37	Accepted	61ms	2996 KiB
		38	Accepted	68ms	3004 KiB
		39	Accepted	94ms	3124 KiB
		40	Accepted	64ms	3004 KiB
		41	Accepted	70ms	2992 KiB
		42	Accepted	41ms	2364 KiB
		43	Accepted	61ms	3124 KiB
		44	Accepted	59ms	3124 KiB
		45	Accepted	64ms	3132 KiB
subtask9	25/25
		46	Accepted	123ms	5836 KiB
		47	Accepted	131ms	5892 KiB
		48	Accepted	119ms	5832 KiB
		49	Accepted	197ms	5908 KiB
		50	Accepted	196ms	5684 KiB
		51	Accepted	195ms	5684 KiB
		52	Accepted	120ms	5940 KiB
		53	Accepted	133ms	5940 KiB
		54	Accepted	135ms	5684 KiB
		55	Accepted	120ms	5684 KiB