fork download
copy 
  1. #include <bits/stdc++.h>
  2. const int N = 1e6;
  3. const int M = 20;
  4. #define ll long long
  5. using namespace std;
  6.  
  7. ll n, m;
  8. int t;
  9. vector<ll> v1, v2;
  10. ll dp[N+3];
  11.  
  12. void build(ll n, ll m){
  13.     n--;
  14.     while(n > 0){
  15.         v1.push_back(n%10);
  16.         n /= 10;
  17.     }
  18.     while(m > 0){
  19.         v2.push_back(m%10);
  20.         m /= 10;
  21.     }
  22.     v1.push_back(0), v2.push_back(0);
  23.     reverse(v1.begin(), v1.end());
  24.     reverse(v2.begin(), v2.end());
  25.  
  26.     dp[1] = 9;
  27.     for(int i=2;i<=M;i++){
  28.         dp[i] = dp[i-1]*9;
  29.     }
  30.     dp[1] = 10;
  31. }
  32.  
  33. ll num(ll n){
  34.     ll res = 1;
  35.     while(n--)res*=9;
  36.     return res;
  37. }
  38.  
  39. ll dpdigit(ll pos, vector<ll> v){
  40.     if(pos == v.size()-1){
  41.         if(v[pos] >= v[pos-1])return v[pos];
  42.         return v[pos] + 1;
  43.     }
  44.     int pos2 = pos + 1;
  45.     if(pos == 1){
  46.         ll sum = v.size() - pos - 1;
  47.         ll ans = 0;
  48.         for(int i=1;i<=sum;i++)ans += dp[i];
  49.         ll xxx = num(sum);
  50.         ans += dpdigit(pos2, v) + xxx*max(0LL, v[pos] - 1);
  51.         return ans;
  52.     }
  53.     ll sum = v.size() - pos - 1;
  54.     ll sumdigit = num(pos);
  55.     if(v[pos] == v[pos - 1])return sumdigit*v[pos];
  56.     else if(v[pos] < v[pos - 1]){
  57.         ll ans = dpdigit(pos2, v) + sumdigit*v[pos];
  58.         return ans;
  59.     }
  60.     ll ans = dpdigit(pos2, v) + sumdigit*max(0LL, v[pos] - 1);
  61.     return ans;
  62. }
  63.  
  64. int main(){
  65.     ios_base::sync_with_stdio(0);
  66.     cin.tie(0);
  67.     cin>>t;
  68.     while(t--){
  69.         cin>>n>>m;
  70.         for(int i=0;i<=M;i++)dp[i] = 0;
  71.         v1.clear(), v2.clear();
  72.         build(n, m);
  73.         ll a, b;
  74.         if(n <= 9)a = n;
  75.         else a = dpdigit(1, v1);
  76.         if(m <= 9)b = m+1;
  77.         else b = dpdigit(1, v2);
  78.         cout<<b - a<<"\n";
  79.     }
  80.  
  81.     return 0;
  82. }
  83.  
Success #stdin #stdout 0.01s 5264KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/946k9n
language:
C++14 (gcc 8.3)
created:
22 hours ago
visibility:
public

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!