Submission #529961

#	Time	Username	Problem	Language	Result	Execution time	Memory
529961		chenyan	Exhibition (JOI19_ho_t2)	C++17	0 / 100	1 ms	332 KiB

joi2019_ho_t2

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define pb emplace_back
#define N 3010
#define ff first
#define ss second
pii a[N];
int f[N],m,ans,id[N],c[N];
vector<int> v,u;
bool ff(int x){
	int j,i;
	bool res=1;
	for(i=x-1,j=m-1;i>=0;i--,j--){
		if(u[i]>c[j]) res=0;
	}
	return res;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,i,j;
	cin>>n>>m;
	for(i=0;i<n;i++) cin>>a[i].ss>>a[i].ff;
	sort(a,a+n);
	for(i=0;i<n;i++){
		auto it=upper_bound(all(v),a[i].ss)-v.begin();
		if(it==v.size()) v.pb(a[i].ss),id[it]=i;
		else v[it]=a[i].ss,id[it]=i;
		if(it)f[i]=id[it-1]+1;
	}
	i=id[v.size()-1];
	while(f[i]){
		u.pb(a[i].ss);
		i=f[i]-1;
	}
	u.pb(a[i].ss);
	sort(all(u));
	sort(all(u));
	for(i=0;i<m;i++) cin>>c[i];
	sort(c,c+m);
	for(i=m,j=0;i;i>>=1){
		while(i+j<=m&&ff(i+j))
			ans=max(ans,i+j),j+=i;
	}
	cout<<ans<<'\n';
}

Compilation message (stderr)

joi2019_ho_t2.cpp: In function 'int main()':
joi2019_ho_t2.cpp:30:8: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   if(it==v.size()) v.pb(a[i].ss),id[it]=i;
      |      ~~^~~~~~~~~~

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