#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));
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:45: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]
45 | while(i+j<u.size()&&ff(i+j))
| ~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
