제출 #1271396

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271396		cmiuc	Exhibition (JOI19_ho_t2)	C++20	50 / 100	1092 ms	2388 KiB

joi2019_ho_t2

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;
const int N = 1<<17;
int dp[N], strt[N];

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, m, ans = 0;
	cin>>n>>m;

	vector<pair<int,int>> vec(n);
	vector<int> c(m);
	
	for (int i=0;i<n;i++)
		cin>>vec[i].second>>vec[i].first;
	sort(begin(vec), end(vec));

	for (int i=0;i<m;i++)
		cin>>c[i];
	sort(begin(c), end(c));

	for (int i=1;i<=n;i++)
		dp[i] = 2e9;

	dp[0] = -1;
	vector<int> stt = {0, 1};
	strt[0] = strt[1] = 1;

	for (auto [b, a] : vec){
		int k = upper_bound(begin(c), end(c), a - 1) - begin(c), upd = 0;
		int u = upper_bound(dp, dp + n + 1, k) - dp;

		// cout<<k<<endl;

		vector<int> add;
		// cout<<"starts : ";
		while (stt.back() >= u and (stt.back() != u or dp[stt.back()] > k + 1)){
			if (u == stt.back())
				upd = 1;
			// cout<<u<<' ';
			int id = stt.back();

			dp[id] = max(dp[id - 1] + 1, k);

			if (dp[id -  1] + 1 >= dp[id])
				strt[id] = 0;

			if (strt[id + 1] == 0 and dp[id + 1] > dp[id] + 1){
				strt[id + 1] = 1;
				add.push_back(id + 1);
			}
			if (strt[id] == 1)
				add.push_back(id);
			stt.pop_back();
		}
		// cout<<'\n';

		if (dp[u] == k + 1 and upd == 0){
			dp[u] = max(k, dp[u-1] + 1);
			if (strt[u + 1] == 0 and dp[u] == k and dp[u+1] == k + 2){
				strt[u + 1] = 1;
				add.push_back(u + 1);
			}
			if (strt[u] and dp[u - 1] >= k - 1){
				stt.pop_back();
				strt[u] = 0;
			}
		}

		reverse(begin(add), end(add));
		for (int i : add)
			stt.push_back(i);

		// for (int i=0;i<=n;i++)
		// 	cout<<i<<" "<<strt[i]<<" "<<dp[i]<<endl;
		// cout<<endl<<endl<<endl;
	}
	for (int i=n;i>=0;i--)
		if (dp[i] < m)
			return cout<<i<<'\n', 0;
}

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