@[Thank_Fine](/user/731423) 用STL里的upper_bound优化一下,否则会RE
by Daben1 @ 2022-08-09 10:47:21
```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2e5;
struct node{
int n,s;
}a[N];
int n,dp[N],cnt=0;
bool cmp(node a,node b){
return a.n<b.n;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].n>>a[i].s;
}
sort(a+1,a+n+1,cmp);
dp[++cnt]=a[1].s;
for(int i=2;i<=n;i++){
if(a[i].s>dp[cnt]) dp[++cnt]=a[i].s;
else{
int loc=upper_bound(dp+1,dp+1+cnt,a[i].s)-dp;
dp[loc]=a[i].s;
}
}
cout<<cnt;
return 0;
}
```
还是WA
by Thank_Fine @ 2022-08-09 10:48:05
已经过了,数据2e5太小了
by Thank_Fine @ 2022-08-09 11:39:22