fork(9) download
  1. // #pragma GCC optimize("Ofast")
  2. // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  3. // #pragma GCC optimize("unroll-loops")
  4. // #pragma comment(linker, "/stack:200000000")
  5. #pragma GCC optimize("O3")
  6. #pragma GCC target ("sse4")
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9. #define int long long
  10. #define F first
  11. #define S second
  12. #define mod 1000000007
  13. #define inf (int)1e18+5
  14. #define sz(x) (int)x.size()
  15. #define PI 3.141592653589793238510
  16. #define all(x) (x).begin(),(x).end()
  17. #define rall(x) (x).rbegin(),(x).rend()
  18. #define __ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  19. #define vi vector<int>
  20. #define vpii vector<pair<int,int> >
  21. #define vvi vector<vector<int> >
  22. #define PRINT_TIME cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s." <<endl;
  23. typedef long double ld;
  24. typedef pair<int,int> pii;
  25. ///////////////////////////////////////////////////////////////////////////////////////////////////
  26. ///////////////////////////////////////////////////////////////////////////////////////////////////
  27. const int N=1e5+5;
  28. int dp[65][2][8][2];
  29. int n;
  30. string s;
  31. int solve(int ind,int lim,int prev,int found){
  32. if(ind==n){
  33. if(prev==5)
  34. found=1;
  35. return found;
  36. }
  37. int &ans=dp[ind][lim][prev][found];
  38. if(ans!=-1)
  39. return ans;
  40. ans=0;
  41. int nxt=0;
  42. int d1=(prev&1),d2=(prev&2);
  43. if(d1){
  44. nxt|=2;
  45. }
  46. if(d2){
  47. nxt|=4;
  48. }
  49. if(prev==5){
  50. found=1;
  51. }
  52. if(lim){
  53. int val=s[ind]-'0';
  54. for(int i=0;i<=val;i++){
  55. ans+=solve(ind+1,i==val,nxt|i,found);
  56. }
  57. }
  58. else{
  59. for(int i=0;i<=1;i++){
  60. ans+=solve(ind+1,0,nxt|i,found);
  61. }
  62. }
  63. return ans;
  64. }
  65. string DTOB(int x){
  66. string ans;
  67. for(int i=0;i<63;i++){
  68. if(x&(1LL<<i))
  69. ans+='1';
  70. else
  71. ans+='0';
  72. }
  73. while(sz(ans) && ans.back()=='0')
  74. ans.pop_back();
  75. if(ans.empty())
  76. ans='0';
  77. reverse(all(ans));
  78. return ans;
  79. }
  80. int32_t main(){__
  81. int te;
  82. cin>>te;
  83. while(te--){
  84. int l,r;
  85. cin>>l>>r; // least value of l should be 1.
  86. l--;
  87. memset(dp,-1,sizeof dp);
  88. s=DTOB(l);
  89. n=sz(s);
  90. // debug()<< imie(s);
  91. int val1=solve(0,1,0,0);
  92. s=DTOB(r);
  93. n=sz(s);
  94. // debug()<< imie(s);
  95. memset(dp,-1,sizeof dp);
  96. int val2=solve(0,1,0,0);
  97. cout<<val2-val1<<"\n";
  98. }
  99. return 0;
  100. }
Success #stdin #stdout 0s 4356KB
stdin
1
1 1000000000000000000
stdout
999507587106663351