oj.uz

Submission #529964

# Submission time Handle Problem Language Result Execution time Memory
529964 2022-02-24T06:54:23 Z chenyan Exhibition (JOI19_ho_t2) C++17
0 / 100
 1 ms 332 KB 
#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 100010
#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));
	for(i=0;i<m;i++) cin>>c[i];
	sort(c,c+m);
	for(i=m,j=0;i;i>>=1){
		while(i+j<=u.size()&&ff(i+j))
			ans=max(ans,i+j),j+=i;
	}
	cout<<ans<<'\n';
}

Compilation message

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;
      |      ~~^~~~~~~~~~
joi2019_ho_t2.cpp:44:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   while(i+j<=u.size()&&ff(i+j))
      |         ~~~^~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Incorrect 0 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Incorrect 0 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Incorrect 0 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -