fork(10) download
copy 
  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
comments (?)
stdin
copy 
1
1 1000000000000000000
stdout
copy 
999507587106663351
https://ideone.com/rTdKUg
language:
C++14 (gcc 8.3)
created:
4 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!