Advertisement
Guest User

Untitled

a guest
Jun 24th, 2019
56
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.60 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define in freopen ("input.txt", "r", stdin);
  3. #define out freopen("output.txt", "w", stdout);
  4. #define ll long long int
  5.  
  6. const int val = (1e6) + 5;
  7. const ll inf = (1e9) + 7;
  8. double eps = 0.000000001;
  9.  
  10. using namespace std;
  11.  
  12. string s;
  13. long long dp[val], sz[val];
  14.  
  15. int ret(int x, int l, int r){
  16.     int m;
  17.     while(l < r){
  18.         m = (l + r) / 2;
  19.         if(dp[m] >= x) r = m;
  20.         else l = m + 1;
  21.     }
  22.     return l;
  23. }
  24.  
  25. long long f(long long x){
  26.     long long st = 1;
  27.     if(x == 1) x = 0;
  28.     while(x > 0){
  29.         st ++;
  30.         x /= 10;
  31.     }
  32.     return st;
  33. }
  34.  
  35. int solve(){
  36.     cin >> s;
  37.     long long t = 0, ans = 0;
  38.     int l = s.size(), r, ln = 0, mz;
  39.     s += '#';
  40.     for(int i=0; i<l; ++i){
  41.         r = i;
  42.         t = 0;
  43.         mz = 1;
  44.         while(isdigit(s[r])){
  45.             t = t * 10 + (s[r] - 48);
  46.             ++ r;
  47.             mz ++;
  48.         }
  49.         t = max(t, 1ll);
  50.         ++ ln;
  51.         dp[ln] = t;
  52.         dp[ln] += dp[ln-1];
  53.         sz[ln] = mz;
  54.         sz[ln] += sz[ln-1];
  55.         i = r;
  56.     }
  57.     int q, l1, l2;
  58.     cin >> q;
  59.     for(int i=0; i<q; ++i){
  60.         long long x, y;
  61.         cin >> x >> y;
  62.         l1 = ret(x, 1, ln);
  63.         l2 = ret(y, 1, ln);
  64.         ans = 0;
  65.         if(l1+1 <= l2-1){
  66.             ans = sz[l2-1] - sz[l1];
  67.         }
  68.         if(l1 == l2) ans += f(y - x + 1);
  69.         else{
  70.             ans += f(dp[l1] - x + 1);
  71.             ans += f(y - dp[l2-1]);
  72.         }
  73.         cout << ans << endl;
  74.     }
  75. }
  76.  
  77. int main(){
  78.     //in out
  79.     ios_base::sync_with_stdio(0);
  80.     solve();
  81.     return 0;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement