// I am teacher of MakaPakka
// LOUGI_ID:643723
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
inline int in(){
int x;
scanf("%d",&x);
return x;
}
#define fi first
#define se second
#define mid ((start+end)/2)
#define pb push_back
#define FOR for(int i=1;i<=n;i++)
#define ort ((bas+son)/2)
const long long inf = 100000000000000;
const int li = 100005;
const int mod = 1000000007;
int n,m,a[li],k,t,cev,b[li],c[li],d[li],tree[li*4];
vector<int> v;
char s[li];
pair<int,int> p[li];
inline void update(int node,int start,int end,int l,int r,int val){
if(start>end || start>r || end<l)return ;
if(start>=l && end<=r){tree[node]=max(tree[node],val);return ;}
update(node*2,start,mid,l,r,val),update(node*2+1,mid+1,end,l,r,val);
tree[node]=max(tree[node*2],tree[node*2+1]);
}
inline int query(int node,int start,int end,int l,int r){
if(start>end || start>r || end<l)return 0;
if(start>=l && end<=r)return tree[node];
return max(query(node*2,start,mid,l,r),query(node*2+1,mid+1,end,l,r));
}
int main(void){
n=in(),m=in();
FOR{
a[i]=in(),b[i]=in();
c[i]=b[i];
}
sort(c+1,c+n+1);
FOR{
int bas=1;
int son=n;
while(bas<=son){
if(b[i]<=c[ort])son=ort-1;
else bas=ort+1;
}
b[i]=bas;
p[i]={a[i],b[i]};
//~ cout<<i<<" :: "<<b[i]<<endl;
}
sort(p+1,p+n+1);
for(int i=1;i<=m;i++){
d[i]=in();
}
sort(d+1,d+m+1);
int yes=m;
for(int i=n;i>=1;i--){
while(yes>0 && d[yes]>=p[i].fi)yes--;
int kal=m-yes;
int at=query(1,1,n,p[i].se,n);
update(1,1,n,p[i].se,p[i].se,min(at+1,kal));
}
printf("%d\n",query(1,1,n,1,n));
return 0;
}
Compilation message
joi2019_ho_t2.cpp: In function 'int in()':
joi2019_ho_t2.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
11 | scanf("%d",&x);
| ~~~~~^~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
316 KB |
Output is correct |
4 |
Correct |
0 ms |
316 KB |
Output is correct |
5 |
Incorrect |
1 ms |
320 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
316 KB |
Output is correct |
4 |
Correct |
0 ms |
316 KB |
Output is correct |
5 |
Incorrect |
1 ms |
320 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
316 KB |
Output is correct |
4 |
Correct |
0 ms |
316 KB |
Output is correct |
5 |
Incorrect |
1 ms |
320 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |