fork download
copy 
  1. // #pragma GCC optimize("Ofast,unroll-loops")
  2. // #pragma GCC target("avx,avx2,fma")
  3.  
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6.  
  7. #define ll long long
  8. #define ull unsigned long long
  9. #define dd double
  10. #define ld long double
  11. #define sl(n) scanf("%lld", &n)
  12. #define si(n) scanf("%d", &n)
  13. #define sd(n) scanf("%lf", &n)
  14. #define pll pair <ll, ll>
  15. #define pii pair <int, int>
  16. #define mp make_pair
  17. #define pb push_back
  18. #define all(v) v.begin(), v.end()
  19. #define inf (1LL << 61)
  20. #define loop(i, start, stop, inc) for(ll i = start; i <= stop; i += inc)
  21. #define for1(i, stop) for(ll i = 1; i <= stop; ++i)
  22. #define for0(i, stop) for(ll i = 0; i < stop; ++i)
  23. #define rep1(i, start) for(ll i = start; i >= 1; --i)
  24. #define rep0(i, start) for(ll i = (start-1); i >= 0; --i)
  25. #define ms(n, i) memset(n, i, sizeof(n))
  26. #define casep(n) printf("Case %lld:", ++n)
  27. #define pn printf("\n")
  28. #define pf printf
  29. #define EL '\n'
  30. #define fastio std::ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  31.  
  32. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  33. // returns a random ll integer in [l, r] range
  34. inline ll gen_random(ll l, ll r) {
  35.     return uniform_int_distribution<ll>(l, r)(rng);
  36. }
  37.  
  38. // === DEBUG MACRO STARTS HERE === //
  39. #ifdef LOCALXOX
  40. #define DEBUG
  41. #define SYS_COL system("COLOR")
  42. #endif
  43.  
  44. int recur_depth = 0;
  45. #ifdef DEBUG
  46. #define dbg(x) {++recur_depth; auto x_=x; --recur_depth; SYS_COL; \
  47.                 cerr<<string(recur_depth, '\t')<<"\e[91m"<<__func__<<":" \
  48.                 <<__LINE__<<"\t"<<#x<<" = "<<x_<<"\e[39m"<<endl;}
  49.  
  50. template<typename Ostream, typename Cont>
  51. typename enable_if<is_same<Ostream,ostream>::value,
  52.             Ostream&>::type operator<<(Ostream& os,  const Cont& v) {
  53. 	os<<"[";
  54. 	for(auto& x:v){os<<x<<", ";}
  55. 	return os<<"]";
  56. }
  57. template<typename Ostream, typename ...Ts>
  58. Ostream& operator<<(Ostream& os,  const pair<Ts...>& p){
  59. 	return os<<"{"<<p.first<<", "<<p.second<<"}";
  60. }
  61. #else
  62. #define dbg(x)
  63. #endif
  64. // === DEBUG MACRO ENDS HERE === //
  65.  
  66. #define ff first
  67. #define ss second
  68.  
  69. ll a, b, c, d;
  70. pll dp[2][2][51][2];
  71. vector <bool> num;
  72.  
  73. pll solve(bool isStart, bool isSmall, ll pos, bool prv)
  74. {
  75.     if(pos == 0)
  76.         return mp(0, 1);
  77.  
  78.     pll &ret = dp[isStart][isSmall][pos][prv];
  79.     if(ret.ff != -1 && isSmall)
  80.         return ret;
  81.  
  82.     ll lim, pos2 = num.size() - pos;
  83.     if(isSmall)
  84.         lim = 1;
  85.     else
  86.         lim = num[pos2];
  87.  
  88.     pll rt = mp(0,0);
  89.  
  90.     if(!isStart) {
  91.         for(ll i = 0; i <= lim; i++) {
  92.             ll pnt = 0;
  93.             if(!isStart) {
  94.                 if(prv==0) pnt = (i==0)? a : b;
  95.                 else pnt = (i==0)? c : d;
  96.             }
  97.  
  98.             pll got = solve(0, isSmall | i < num[pos2], pos - 1, i);
  99.  
  100.             rt.ff += pnt*got.ss + got.ff, rt.ss += got.ss;
  101.         }
  102.     }
  103.     else {
  104.         for(ll i = 1; i <= lim; i++) {
  105.             ll pnt = 0;
  106.             if(!isStart) {
  107.                 if(prv==0) pnt = (i==0)? a : b;
  108.                 else pnt = (i==0)? c : d;
  109.             }
  110.  
  111.             pll got = solve(0, isSmall | i < num[pos2], pos - 1, i);
  112.  
  113.             rt.ff += pnt*got.ss + got.ff, rt.ss += got.ss;
  114.         }
  115.  
  116.         pll got = solve(1, 1, pos - 1, 0);
  117.         rt.ff += got.ff, rt.ss += got.ss;
  118.     }
  119.  
  120.     return ret = rt;
  121. }
  122.  
  123. ll calc(ll n)
  124. {
  125.     if(n < 1) return 0;
  126.  
  127.     ll tmp = n;
  128.     num.clear();
  129.     while(tmp) {
  130.         num.pb(tmp%2);
  131.         tmp /= 2;
  132.     }
  133.     reverse(num.begin(), num.end());
  134.  
  135.     return solve(1, 0, num.size(), 0).ff;
  136. }
  137.  
  138. int main()
  139. {
  140.     fastio;
  141.     ll t;
  142.     cin >> t;
  143.  
  144.     while(t--) {
  145.         ll l, r;
  146.         cin >> l >> r;
  147.  
  148.         cin >> a >> b >> c >> d;
  149.  
  150.         ms(dp, -1);
  151.         ll ans = calc(r);
  152.         ans -= calc(l-1);
  153.  
  154.         cout << ans << EL;
  155.     }
  156.  
  157.     return 0;
  158. }
  159.  
Success #stdin #stdout 0s 5536KB
comments (?)
stdin
copy 
2
1 2
5 1 3 2
2 5
4 12 3 3
stdout
copy 
3
28
https://ideone.com/Z5KAJ8
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

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!