Submission #75817737

---

Source Code Expand

#include <bits/stdc++.h>
#pragma GCC optimize("O3,fast-math")
using namespace std;
using ll = long long;
int n,q,L,R,x[303030],r[303030],l[303030],dupli[303030];
string s;
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    cin >> s;

    for(int i=1;i<=n;i++) if(s[i-1]=='X') x[i]++;
    for(int i=1;i<=n;i++) x[i]+=x[i-1]; // prefix sum

    for(int i=1;i<=n;) {
        int cnt=0, pos=i;
        if(s[i-1]=='X') {
            i++; continue;
        }

        while(i<=n && s[i-1]==s[pos-1]) cnt++, i++;
        if(cnt==1) continue;
        dupli[pos]=cnt/2;
        for(int j=pos;j<i;j++) l[j]=pos-1, r[j]=i;
    }
    for(int i=1;i<=n;i++) dupli[i]+=dupli[i-1];

    //for(int i=1;i<=n;i++) cout << l[i] << " "; cout << "\n";
    //for(int i=1;i<=n;i++) cout << r[i] << " "; cout << endl;
    while(q--) {
        cin >> L >> R;
        int ol=L, orr=R;
        int ans=0;
    
        if(r[L]) ans+=(r[L]-L)/2, L=r[L];
        if(l[R]) ans+=(R-l[R])/2, R=l[R];
        if(L>R+1) {// exception
            cout << (orr-ol+1)/2 << "\n";
            continue;
        }
        //cout << L << R << endl;
        //ans+=x[R]-x[L-1];
        ans+=dupli[R]-dupli[L-1];
        cout << ans << "\n";
        //cout << endl;
    }
}

Submission Info

Judge Result