제출 #1271389

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271389		cmiuc	Exhibition (JOI19_ho_t2)	C++20	50 / 100	1095 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;
	set<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;

		auto pntr = prev(end(stt));
		vector<int> ers, ins;
		while (*pntr >= u and (*pntr != u or dp[*pntr] > k + 1)){
			if (u == *pntr)
				upd = 1;
			int id = *pntr;
			// cout<<id<<" "<<dp[id]<<' ';
			dp[id] = max(dp[id - 1] + 1, k);
			// cout<<dp[id]<<" kdks "<<endl;
			if (dp[id -  1] + 1 >= dp[id])
				strt[id] = 0, ers.push_back(id);

			if (strt[id + 1] == 0 and dp[id + 1] > dp[id] + 1){
				strt[id + 1] = 1;
				ins.push_back(id + 1);
			}
			// ers.push_back(id);

			pntr = prev(pntr);
		}

		auto prv = prev(stt.upper_bound(u - 1));

		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;
				ins.push_back(u + 1);
			}
			if (strt[u] and dp[u - 1] >= k - 1){
				ers.push_back(u);
				strt[u] = 0;
			}
		}

		for (int i : ers)
			stt.erase(i);
		for (int i : ins)
			stt.insert(i);

		// for (int i=0;i<=n;i++)
		// 	cout<<i<<" "<<strt[i]<<" "<<dp[i]<<'\n';
		// 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