Source Code
#define ll long long
#define fr first
#define sc second
#define pb(x) push_back(x)
#define nxt continue
#define sz(container) ((ll) container.size())
#define umap unordered_map
#define uset unordered_set
#define MAX LONG_LONG_MAX
#define MIN LONG_LONG_MIN
#define mkpr(f, s) make_pair(f, s)
#define el '\n'
#define pq priority_queue

#include <bits/stdc++.h>
using namespace std;

const ll MOD = 1e9;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  
  string s;
  
  cin >> s;
  
  ll gg[]{8, 4, 2, 6};
  
  vector<vector<ll>> pre(4, vector<ll>(sz(s) / 4 + 1));
  
  ll i = -1, cnt = 0, j, c, ans, rr, le, mod;
  
  for (char& c : s) {
    if (!cnt) {
      ++i;
    }
    
    if (c == '1')
      for (j = 0; j < 4; ++j) {
        pre[j][i] += gg[(cnt + j) % 4];
      }
    
    cnt = (cnt + 1) % 4;
  }
  
  for (auto& p : pre) {
    for (i = 1; i < sz(s) /4 + 1; ++i) {
      p[i] += p[i - 1];
    }
  }
  
//  for (auto& p : pre) {
//    for (i = 0; i < sz(s) / 4 + 1; ++i) {
//      cout << p[i] << ' ';
//    }
//    cout << el;
//  }
  
//  cout << el;
  
  ll q, l, r;
  
  cin >> q;
  
  while (q--) {
    cin >> l >> r;
    
    --r, --l;
    
    ans = 0;
    
    if (r - l + 1 <= 4) {
      for (c = 1; r >= l; --r) {
        if (s[r] == '1') {
          ans += c;
        }
        c *= 2;
      }
    } else {
      rr = r / 4 - 1;
      le = l / 4;
      
      mod = (4 - (r + 1) % 4) % 4;
      
      ans += pre[mod][rr] - pre[mod][le];
      
      for (c = 1, i = r; i >= r / 4 * 4; --i, c *= 2) {
        if (s[i] == '1') {
          ans += c;
        }
      }
      
      cnt = 0;
      ll ggg[]{6, 2, 4, 8};
      for (i = (l / 4 + 1) * 4 - 1; i >= l; --i, ++cnt) {
        if (s[i] == 1) {
          ans += gg[(mod + cnt) % 4];
        }
      }
      
//      cout << pre[mod][rr] - pre[mod][le] << el;
    }
    
    cout << ans % 10 << el;
  }
  
  return 0;
}
Copy
Binarithm Nedal
GNU G++17
96 ms
2.5 MB
Wrong Answer