Submission #1169609

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169609		lufychop	Exhibition (JOI19_ho_t2)	C++20	0 / 100	0 ms	328 KiB

joi2019_ho_t2

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
	int n,m,s,v,c;
	cin>>n>>m;
	set<int> frameset;
	vector<int> frame;
	vector<int> lnds,lnds2;
	vector<int> frameleft;
	vector<pair<int,int>> x;
	for(int i=0;i<n;i++)
	{
		cin>>s>>v;
		x.push_back({v,s});
	}
	for(int i=0;i<m;i++)
	{
		cin>>c;
		frame.push_back(c);
	}
	sort(x.begin(),x.end());
	for(int i=0;i<n;i++)
	{
		swap(x[i].first,x[i].second);
		//cout<<x[i].first<<" "<<x[i].second<<"\n";
	}
	sort(frame.begin(),frame.end());
	frameleft.push_back(1);
	for(int i=1;i<m;i++)
	{
		if(frame[i]!=frame[i-1])
		{
			frameleft.push_back(1);
		}
		else
		{
			frameleft[frameleft.size()-1]++;
		}
	}
	frame.erase(unique(frame.begin(),frame.end()),frame.end());
	m=frame.size();
	for(int i=0;i<m;i++)
	{
		frameset.insert(frame[i]);
		//cout<<frame[i]<<" "<<frameleft[i]<<"\n";
	}
	for(int i=0;i<n;i++)
	{
		set<int>::iterator itr=frameset.lower_bound(x[i].first),itr2;
		int fi=lower_bound(frame.begin(),frame.end(),*itr)-frame.begin();
		int x2,fi2;
		if(itr==frameset.end())
		{
			continue;
		}
		if(lnds.empty()||lnds.back()<=x[i].first)
		{
			if(itr==frameset.end())
			{
				//cout<<frameset.size()<<" ";
				continue;
			}
			//cout<<x[i].first<<" "<<*itr<<"\n";
			frameleft[fi]--;
			lnds.push_back(x[i].first);
			lnds2.push_back(fi);
			if(frameleft[fi]==0)
			{
				frameset.erase(itr);
			}
		}
		else
		{
			fi2=upper_bound(lnds.begin(),lnds.end(),x[i].first)-lnds.begin();
			frameleft[lnds2[fi2]]++;
			frameset.insert(frame[fi]);
			itr2=frameset.lower_bound(x[i].first);
			fi=lower_bound(frame.begin(),frame.end(),*itr)-frameleft.begin();
			frameleft[fi--];
			lnds[fi2]=x[i].first;
			lnds2[fi2]=fi;
			if(frameleft[fi]==0)
			{
				frameset.erase(itr2);
			}
		}
	}
	cout<<lnds.size();
	return 0;
}
/*
3 4
10 20
5 1
3 5
4
6
10
4

4 4 6 10
5 3 10

4 5 7 7 7 4 3 3 3 4 4

3 2
1 2
1 2
1 2
1
1

8 8
9 3
8 8
7 2
15 5
14 4
12 7
10 1
3 6
4
16
1
13
5
6
11
2

 1 2 4 5 6 11 13 16
10 7 9 14 15 3 12 8

11 13 16
 7  9 14
10  9 14



8 8
508917604 35617051
501958939 840246141
485338402 32896484
957730250 357542366
904165504 137209882
684085683 775621730
552953629 20004459
125090903 607302990
433255278
979756183
28423637
856448848
276518245
314201319
666094038
149542543
*/

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