fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int long long
  6. typedef pair<int, int> pp;
  7. #define all(a) (a).begin(), (a).end()
  8. #define what_is(x) cerr << #x << " is " << x << '\n';
  9. #define print(a) for (const auto &x : (a)) cout << x << ' '; cout << '\n';
  10. const int N = 2e5 + 7;
  11. const int MOD = 1e9 + 7;
  12. const int INF = 1e15;
  13.  
  14.  
  15. array<int, 3> mem[16][2][2] {};
  16. bool vis[16][2][2] {};
  17. int mx = 0;
  18. string num;
  19.  
  20. array<int, 3> dp(int i, bool st, bool sm) {
  21.     if (i == num.size()) return {0, (st ? 1 : 0), 0};
  22.     if (vis[i][st][sm]) return mem[i][st][sm];
  23.     vis[i][st][sm] = true;
  24.     int ret = 0, count = 0,  dd = 0;
  25.     ret = 0;
  26.     if (!st) {
  27.         array<int, 3> p = dp(i + 1, st, 1);
  28.         ret = p[0];
  29.         count = p[1];
  30.         dd = p[2];
  31.     }
  32.  
  33.     int x = num[i] - '0';
  34.     for (int d = 0; d < 10; ++d) {
  35.         if (!st and !d) continue;
  36.         if (!sm and d > x) break;
  37.  
  38.         // the number in which this value will contribute
  39.         if (d == mx) {
  40.             array<int, 3> p = dp(i + 1, 1, sm || (d < x));
  41.             ret += p[0];
  42.             dd += p[2] + p[1];
  43.             count += p[1];
  44.         } else if (d > mx) {
  45.             array<int, 3> p = dp(i + 1, 1, sm || (d < x));
  46.             ret += p[0] + p[2];
  47.             count += p[1];
  48.             dd += p[2];
  49.         } else {
  50.             array<int, 3> p = dp(i + 1, 1, sm || (d < x));
  51.             ret += p[0];
  52.             count += p[1];
  53.             dd += p[2];
  54.         }
  55.     }
  56.     return mem[i][st][sm] = {ret, count, dd};
  57. }
  58. int count_inv(int n) {
  59.     num = to_string(n);
  60.     memset(vis, false, sizeof(vis));
  61.     return dp(0, 0, 0)[0];
  62. }
  63. void solve() {
  64.     int l, r; cin >> l >> r;
  65.     int ans = 0;
  66.     for (mx = 0; mx < 9; ++mx) {
  67.         ans += count_inv(r) - count_inv(l - 1);
  68.     }
  69.     cout << ans << '\n';
  70. }
  71.  
  72. int32_t main() {
  73.     ios_base::sync_with_stdio(false);
  74.     cin.tie(nullptr);
  75.     cout.tie(nullptr);
  76.  
  77. #ifndef ONLINE_JUDGE
  78.     freopen("input.txt", "r", stdin);
  79.     freopen("output.txt", "w", stdout);
  80. #endif
  81.  
  82.     int tt = 1;
  83.     cin >> tt;
  84.     while (tt--) {
  85.         solve();
  86.     }
  87.  
  88.     return 0;
  89. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-813186878855040
https://ideone.com/fcngOz
language:
C++14 (gcc 8.3)
created:
4 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!