This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
#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; }