fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define f first
  4. #define s second
  5. #define pb push_back
  6. #define pob pop_back
  7. #define b back
  8. #define cout(x) cout << x << endl
  9. #define lb long double
  10. #define soa(arr, n) sort(arr,arr+n)
  11. #define inputVector(v, n) for(ll i = 0; i < n; i++) cin >> v[i]
  12. #define sov(v) sort(v.begin(), v.end())
  13. #define rev(v) reverse(v.begin(), v.end())
  14. #define pl pair<ll, ll>
  15. #define all(a)    a.begin(), a.end()
  16. #define vpp vector<pair<ll, ll>>
  17. #define fastIo ios_base::sync_with_stdio(false), cin.tie(0)
  18. // #define endl '\n'
  19. #define No cout << "NO\n"; 
  20. #define Yes cout << "YES\n";
  21. typedef long long int  ll;
  22.  
  23. ll P = 998244353;
  24.  
  25.  
  26. bool can_convert(string &s, string & t, int ind, int l, int r) {
  27.     ind --;
  28.     l --;
  29.     r --;
  30.     if(s[ind] == '1') return true;
  31.  
  32.     ll t_l = t[ind - 1];
  33.     ll t_r = t[ind + 1];
  34.  
  35.     if(ind - 1 >= l && ind + 1 <= r) {
  36.         char t_l = t[ind - 1];
  37.         char t_r = t[ind + 1];
  38.  
  39.         if(t_l == '0') {
  40.             return false;
  41.         }
  42.  
  43.         if(s[ind] == '0' && ind + 2 <= r && s[ind + 2] == '0') {
  44.             return true;
  45.         }
  46.     }
  47.     return false;
  48. }
  49.  
  50.  
  51. void solve() {
  52.     ll n, c;
  53.     cin >> n;
  54.     string s, t;
  55.     cin >> s >> t;
  56.  
  57.     string s1 = s, t1 = t;
  58.     for(ll i = 0; i < n - 2; i ++) {
  59.         if(s1[i] == s1[i + 2] && s1[i] == '0') {
  60.             t1[i + 1] = '1';
  61.         }
  62.     }
  63.  
  64.     for(ll i = 0; i < n - 2; i ++) {
  65.         if(t1[i] == t1[i + 2] && t1[i] == '1') {
  66.             s1[i + 1] = '1';
  67.         }
  68.     }
  69.  
  70.     // cout << s1 << " " << t1 << endl;
  71.     vector<ll> pref(n + 1);
  72.     for(ll i = 0; i < n; i++) {
  73.         pref[i + 1] = pref[i] + (s1[i] == '1');
  74.     }
  75.  
  76.     ll q;
  77.     cin >> q;
  78.     while(q --) {
  79.         ll l, r;
  80.         cin >> l >> r;
  81.         ll cnt = 0;
  82.         if(r >= 2 && r >= l + 2 && pref[r - 2] -pref[l + 1] >= 0) {
  83.             cnt = pref[r - 2] -pref[l + 1];
  84.         }
  85.         if(cnt < 0) cnt = 0;
  86.         // cout << " debug " << cnt << endl;
  87.  
  88.         cnt += s[l - 1] == '1';
  89.         if(r - 1 != l - 1) {
  90.             cnt += s[r - 1] == '1';
  91.         }
  92.  
  93.  
  94.         if(l + 1 <= r - 1) {
  95.             cnt += can_convert(s, t, l + 1, l, r);
  96.              if(r - 1 != l + 1) {
  97.                 cnt += can_convert(s, t, r - 1, l, r);
  98.             }
  99.         }
  100.  
  101.         cout << cnt << endl;
  102.  
  103.  
  104.     }
  105.  
  106.  
  107. }
  108.  
  109.  int main() {
  110.     ll t=1,i=1, n, p, l, T;
  111.  
  112.     cin >> t;
  113.  
  114.     while(t--) {
  115.         solve();
  116.     }
  117.     return 0;
  118. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
3
4
1111
0000
2
1 2
2 4
4
1010
1101
2
1 3
1 4
6
010101
011010
5
2 3
1 6
2 5
4 4
3 6
stdout
copy 
2
3
2
3
1
4
3
1
2
https://ideone.com/PApbrg
language:
C++14 (gcc 8.3)
created:
189 days ago
visibility:
secret

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!