fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define Hoshimachi signed
  3. #define Suisei main
  4. using namespace std;
  5. #define int long long
  6. #define pii pair<int,int>
  7. int h,k,ans=0;
  8. bool cmp(pii a, pii b){
  9.     return a.first*b.second<a.second*b.first;
  10. }
  11. vector<pii> v;
  12. void dfs(pii a, pii pl, pii pr, int st, int ed){
  13.     int l=st,r=ed,m,kq=-1;
  14.     while(l<=r){
  15.         m=(l+r)/2;
  16.         if(cmp(v[m],a)){
  17.             l=m+1;
  18.             kq=m;
  19.         }
  20.         else{
  21.             r=m-1;
  22.         }
  23.     }
  24.     int edl=kq;
  25.     l=st,r=ed,kq=1e9;
  26.     while(l<=r){
  27.         m=(l+r)/2;
  28.         if(cmp(a,v[m])){
  29.             r=m-1;
  30.             kq=m;
  31.         }
  32.         else{
  33.             l=m+1;
  34.         }
  35.     }
  36.     int str=kq;
  37.     pii al={a.first+pl.first,a.second+pl.second};
  38.     pii ar={a.first+pr.first,a.second+pr.second};
  39.     if(edl>=st){
  40.         dfs(al,pl,a,st,edl);
  41.         ans++;
  42.     }
  43.     if(str<=ed){
  44.         dfs(ar,a,pr,str,ed);
  45.         ans++;
  46.     }
  47. }
  48. Hoshimachi Suisei(){
  49.     ios_base::sync_with_stdio(0);
  50.     cin.tie(0); cout.tie(0);
  51.     // freopen(".inp", "r", stdin);
  52.     // freopen(".out", "w", stdout);
  53.     cin>>h>>k;
  54.     for(int i=1; i<=k; i++){
  55.         int a,b;
  56.         cin>>a>>b;
  57.         v.push_back({a,b});
  58.     }
  59.     sort(v.begin(),v.end(),cmp);
  60.     v.erase(unique(v.begin(),v.end()),v.end());
  61.     dfs({1,1},{0,1},{1,0},0,v.size()-1);
  62.     cout<<ans;
  63. }
  64.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/QPnp38
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!