#include<bits/stdc++.h>
#define fi first
#define se second
#define show(x) cerr<<#x<<"="<<x<<"\n"
typedef long long ll;
using namespace std;
class Bit{
public:
explicit Bit(int n):size(static_cast<unsigned int>(n)){
tbl.resize(size+10,0);
}
void add(int a,ll w){
for(int i=a;i<=size;i+=i&-i)tbl[i]=max(tbl[i],w);
}
ll sum(int a){
ll ret=0;
if(a==0)return 0;
for(int i=a;i>0;i-=i&-i){
ret=max(ret,tbl[i]);
}
return ret;
}
int lower_bound(ll w){
if(w<=0)return 0;
int x=0;
int k=1;
while(true){
if(k*2>size){
break;
}
k*=2;
}
for(k;k>0;k/=2){
if(x+k<=size && tbl[x+k]<w){
w-=tbl[x+k];
x+=k;
}
}
return x+1;
}
private:
unsigned int size;
vector<ll> tbl;
};
int n,m,h,w;
vector<pair<int,int> > v;
int dp[100001];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.precision(10);
cout<<fixed;
#ifdef LOCAL_DEFINE
FILE *stream1;
stream1=freopen("in","r",stdin);
if(stream1==NULL)return 0;
#endif
cin>>n;
for(int i=0;i<n;i++){
int h,w;cin>>h>>w;
v.push_back({h,-w});
}
sort(v.begin(),v.end());
Bit bit(100001);
for(int i=0;i<n;i++){
dp[i]=bit.sum(-v[i].se-1)+1;
bit.add(-v[i].se,dp[i]);
}
int ans=0;
for(int i=0;i<n;i++){
ans=max(ans,dp[i]);
}
cout<<ans<<endl;
#ifdef LOCAL_DEFINE
cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
fclose(stream1);
#endif
return 0;
}
- ソートするは良いけど、そこから思いつかなかった。
- hが同じ時wを降順にするの、おぉ!ってなった
- bitのライブラリ作ってあったから、その場で作り変えて実装させることができた。
- ライブラリがあると本当に便利よねー
- w[i]より小さい最大のdpの大きさ、、、、そんな考え方は出来なかった。
- 未来の自分に向けて言いますが、あなたはおそらくこの問題をいつか復習する際また同じようなところで引っかかってこのブログのページに帰ってくるでしょう。