test/aoj/2646.test.cpp

• View this file on GitHub
• Last update: 2020-10-27 14:01:51+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2646

Depends on

• datastructure/pb_ds_cc_hash_table.cpp
• tools/cc_hash.cpp
• tools/fixpoint.cpp

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2646"

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#include "../../tools/fixpoint.cpp"
#include "../../tools/cc_hash.cpp"
#include "../../datastructure/pb_ds_cc_hash_table.cpp"
#undef call_from_test

#ifdef SANITIZE
#define IGNORE
#endif

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  using ll = long long;

  int n,m;
  cin>>n>>m;

  m++;
  vector<int> as(m),bs(m);
  for(int i=0;i<m;i++) cin>>as[i];
  for(int i=1;i<m;i++) cin>>bs[i];

  vector<ll> hs;
  MFP([&](auto dfs,int l,int r)->void{
        int x=lower_bound(as.begin(),as.end(),r)-as.begin();
        if(as[x-1]<=l&&r<=as[x]) return;
        hs.emplace_back(((ll)l<<31)|r);
        int m=(l+r)>>1;
        dfs(l,m);
        dfs(m,r);
      })(0,(1<<n));

  sort(hs.begin(),hs.end());
  hs.erase(unique(hs.begin(),hs.end()),hs.end());

  gmap<ll, int, cc_hash<ll> > idx;
  for(int i=0;i<(int)hs.size();i++) idx[hs[i]]=i;

  vector< vector<int> > dp(n+1,vector<int>(hs.size(),-1));

  int ans=(1<<n)-
    MFP([&](auto dfs,int l,int r,int d,int k)->int{
          int x=lower_bound(as.begin(),as.end(),r)-as.begin();
          if(as[x-1]<=l&&r<=as[x]){
            int v=bs[x],tmp=0;
            tmp+=(k==v);
            tmp+=(r-l)>>(n-v+1);
            return tmp;
          }

          if(~dp[k][idx[((ll)l<<31)|r]]) return dp[k][idx[((ll)l<<31)|r]];
          int &res=(dp[k][idx[((ll)l<<31)|r]]=0);

          int m=(l+r)>>1;
          res=max(res,dfs(l,m,d+1,d)+dfs(m,r,d+1,k));
          res=max(res,dfs(l,m,d+1,k)+dfs(m,r,d+1,d));
          return res;
        })(0,1<<n,1,0);

  cout<<ans<<endl;
  return 0;
}

#line 1 "test/aoj/2646.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2646"

#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#line 1 "tools/fixpoint.cpp"

#line 3 "tools/fixpoint.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template<typename F>
struct FixPoint : F{
  FixPoint(F&& f):F(forward<F>(f)){}
  template<typename... Args>
  decltype(auto) operator()(Args&&... args) const{
    return F::operator()(*this,forward<Args>(args)...);
  }
};
template<typename F>
inline decltype(auto) MFP(F&& f){
  return FixPoint<F>{forward<F>(f)};
}
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
#line 1 "tools/cc_hash.cpp"

#line 3 "tools/cc_hash.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T>
struct cc_hash{
  uint64_t operator()(T x) const{
    uint64_t y(x);
    y += 0x9e3779b97f4a7c15;
    y = (y ^ (y >> 30)) * 0xbf58476d1ce4e5b9;
    y = (y ^ (y >> 27)) * 0x94d049bb133111eb;
    return y ^ (y >> 31);
  }
};
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 1 "datastructure/pb_ds_cc_hash_table.cpp"

#line 3 "datastructure/pb_ds_cc_hash_table.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<typename T,typename U, typename H=hash<T> >
using gmap = cc_hash_table<T, U, H>;
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
#line 10 "test/aoj/2646.test.cpp"
#undef call_from_test

#ifdef SANITIZE
#define IGNORE
#endif

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  using ll = long long;

  int n,m;
  cin>>n>>m;

  m++;
  vector<int> as(m),bs(m);
  for(int i=0;i<m;i++) cin>>as[i];
  for(int i=1;i<m;i++) cin>>bs[i];

  vector<ll> hs;
  MFP([&](auto dfs,int l,int r)->void{
        int x=lower_bound(as.begin(),as.end(),r)-as.begin();
        if(as[x-1]<=l&&r<=as[x]) return;
        hs.emplace_back(((ll)l<<31)|r);
        int m=(l+r)>>1;
        dfs(l,m);
        dfs(m,r);
      })(0,(1<<n));

  sort(hs.begin(),hs.end());
  hs.erase(unique(hs.begin(),hs.end()),hs.end());

  gmap<ll, int, cc_hash<ll> > idx;
  for(int i=0;i<(int)hs.size();i++) idx[hs[i]]=i;

  vector< vector<int> > dp(n+1,vector<int>(hs.size(),-1));

  int ans=(1<<n)-
    MFP([&](auto dfs,int l,int r,int d,int k)->int{
          int x=lower_bound(as.begin(),as.end(),r)-as.begin();
          if(as[x-1]<=l&&r<=as[x]){
            int v=bs[x],tmp=0;
            tmp+=(k==v);
            tmp+=(r-l)>>(n-v+1);
            return tmp;
          }

          if(~dp[k][idx[((ll)l<<31)|r]]) return dp[k][idx[((ll)l<<31)|r]];
          int &res=(dp[k][idx[((ll)l<<31)|r]]=0);

          int m=(l+r)>>1;
          res=max(res,dfs(l,m,d+1,d)+dfs(m,r,d+1,k));
          res=max(res,dfs(l,m,d+1,k)+dfs(m,r,d+1,d));
          return res;
        })(0,1<<n,1,0);

  cout<<ans<<endl;
  return 0;
}

Back to top page