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. pp mem[16][16][2][2] {};
  16. bool vis[16][16][2][2] {};
  17. int mx = 0;
  18. string num;
  19.  
  20. pp dp(int i, int bigger, bool st, bool sm) {
  21.     if (i == num.size()) return {0, (st ? 1 : 0)};
  22.  
  23.     if (vis[i][bigger][st][sm]) return mem[i][bigger][st][sm];
  24.     vis[i][bigger][st][sm] = true;
  25.  
  26.     int ret = 0, count = 0;
  27.  
  28.  
  29.  
  30.     ret = 0;
  31.     if (!st) {
  32.         pp p = dp(i + 1, bigger, st, 1);
  33.         ret = p.first;
  34.         count = p.second;
  35.     }
  36.  
  37.     int x = num[i] - '0';
  38.     for (int d = 0; d < 10; ++d) {
  39.         if (!st and !d) continue;
  40.         if (!sm and d > x) break;
  41.  
  42.         // the number in which this value will contribute
  43.         if (d == mx) {
  44.             pp p = dp(i + 1, bigger, 1, sm || (d < x));
  45.             ret += p.second * bigger + p.first;
  46.             count += p.second;
  47.  
  48.         } else {
  49.             pp p = dp(i + 1, bigger + (d > mx), 1, sm | (d < x));
  50.             ret += p.first;
  51.             count += p.second;
  52.         }
  53.     }
  54.     return mem[i][bigger][st][sm] = {ret, count};
  55. }
  56.  
  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).first;
  62. }
  63.  
  64.  
  65. void solve() {
  66.     int l, r; cin >> l >> r;
  67.  
  68.     int ans = 0;
  69.     for (mx = 0; mx < 10; ++mx) {
  70.         ans += count_inv(r) - count_inv(l - 1);
  71.     }
  72.     cout << ans << '\n';
  73.  
  74. }
  75.  
  76. int32_t main() {
  77.     ios_base::sync_with_stdio(false);
  78.     cin.tie(nullptr);
  79.     cout.tie(nullptr);
  80.  
  81. #ifndef ONLINE_JUDGE
  82.     freopen("input.txt", "r", stdin);
  83.     freopen("output.txt", "w", stdout);
  84. #endif
  85.  
  86.     int tt = 1;
  87.     cin >> tt;
  88.     while (tt--) {
  89.         solve();
  90.     }
  91.  
  92.     return 0;
  93. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-823699899590344
https://ideone.com/g3QZTp
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!