Source Code
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define EPS 1e-6
#define Ceil(n, m) ((n / m) + ( n % m ? 1 : 0))
#define mod 1000000007
#define over 1e18
#define cin(v) for(auto &i: v)  cin>>i
#define cout(v) for(auto &i: v) cout<<i<<" ";
#define all(v) v.begin(), v.end()
#define LSB(n) (n & -n)
#define OO 2'000'000'000
void fcode(){
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
   /* #ifndef ONLINE_JUDGE
      freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout) ,  freopen("error.txt", "w", stderr);
    #endif*/
}
int main(){
    fcode();
    string s;    cin>>s;
    vector<int>pos;
    for(int i = 0; i<s.size(); i++)
      if(s[i] == '1') pos.emplace_back(i);
    
    int q;    cin>>q;
    while(q--){
      int l, r;    cin>>l>>r;
      ll num = 0;
      l--, r--;
      ll end = lower_bound(all(pos), l) - pos.begin();
      ll beg = lower_bound(all(pos), r) - pos.begin();
      if(pos[beg] > r) beg--;
      if(pos[end] < l) end++;
       for(int i = beg, j = r - pos[beg]; i>= end;i--){
           num |= (1 <<j);
           j += abs(pos[i] - pos[i-1]);
           num %= 100;
       }
       cout<<num % 10<<"\n";
      }
}
Copy
Binarithm Hodakamal
GNU G++17
2068 ms
1.1 MB
Time Limit Exceeded