ABC038-D プレゼント

#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:
    //tbl[1]...tbl[n]
    explicit Bit(int n):size(static_cast<unsigned int>(n)){//1-indexed
        tbl.resize(size+10,0);
    }
    
    //一点のみの更新
    void add(int a,ll w){//tbl[a]+=w , 1-indexed , 1-indexed!!!!!!!!!!!!!!!
        for(int i=a;i<=size;i+=i&-i)tbl[i]=max(tbl[i],w);
    }

    ll sum(int a){//v[1]+...+v[a] , 1-indexed ,1-indexed!!!!!!!!!!!!!
        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;//1-indexed , 1-indexed!!!!!!!!!!!!
    }
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;
  //FILE *stream2;
  stream1=freopen("in","r",stdin);
  //stream2=freopen("out","w",stdout);
  if(stream1==NULL)return 0;
  //if(stream2==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);
  //fclose(stream2);
#endif
  return 0;
}

• ソートするは良いけど、そこから思いつかなかった。
• hが同じ時wを降順にするの、おぉ！ってなった
• bitのライブラリ作ってあったから、その場で作り変えて実装させることができた。
• ライブラリがあると本当に便利よねー
• w[i]より小さい最大のdpの大きさ、、、、そんな考え方は出来なかった。
• 未来の自分に向けて言いますが、あなたはおそらくこの問題をいつか復習する際また同じようなところで引っかかってこのブログのページに帰ってくるでしょう。