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>((ll) 1e5));
  
  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];
    }
  }
  
  ll q, l, r;
  
  cin >> q;
  
  while (q--) {
    cin >> l >> r;
    
    --r, --l;
    
    if (r - l + 1 <= 4) {
      c = 1, ans = 0;
      
      for (; r >= l; --r) {
        if (s[r] == '1') {
          ans += c;
        }
        c *= 2;
      }
      
      cout << ans % 10 << el;
    } else {
      rr = r / 4 - 1;
      le = l / 4;
      mod = (r + 1) % 4;
//      cout << rr << ' ' << le << el;
      ans = pre[mod][rr] - pre[mod][le];
      
      c = 1;
      
      for (; r >= r / 4 * 4; --r) {
        if (s[r] == '1') {
          ans += c;
        }
        c *= 2;
      }
      
//      for (i = (l / 4 + 1) * 4 - 1, j = 3; i >= l; --i, --j) {
//        if (s[i] == '1') {
//          ans += gg[(j - mod + 4) % 4];
//        }
//      }
      
      cout << ans % 10 << el;
    }
  }
  
  return 0;
}
Copy
Binarithm Nedal
GNU G++17
5 ms
4.1 MB
Wrong Answer