Submission #75819533

---

Source Code Expand

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

// https://github.com/skrewbar/cp-templates

#define all(v) (v).begin(), (v).end()
#define compress(v) \
    sort(all(v));   \
    v.erase(unique(all(v)), (v).end())
#define by(x) [](const auto& a, const auto& b) { return a.x < b.x; }
#define by_desc(x) [](const auto& a, const auto& b) { return a.x > b.x; }

template <typename T>
using MinHeap = priority_queue<T, vector<T>, greater<T>>;

template <typename T>
bool minimize(T& target, T candidate) {
    return target > candidate ? (target = candidate, true) : false;
}
template <typename T>
bool maximize(T& target, T candidate) {
    return target < candidate ? (target = candidate, true) : false;
}

int dp[303030];
int groupStart[303030];
int groupEnd[303030];
int groupNum[303030];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;

    string S;
    cin >> S;
    S = "#" + S;

    int groupCnt = 0;
    for (int i = 1, j; i <= N; i = j) {
        j = i + 1;
        while (j <= N and S[j] == S[i])
            j++;

        groupCnt++;

        groupStart[groupCnt] = i;
        groupEnd[groupCnt] = j - 1;
        for (int k = i; k < j; k++)
            groupNum[k] = groupCnt;
    }

    for (int i = 1; i <= N; i = groupEnd[groupNum[i]] + 1) {
        int num = groupNum[i];
        dp[num] = dp[num - 1];
        
        if (S[i] != 'X')
            dp[num] += (groupEnd[num] - groupStart[num] + 1) / 2;
    }

    while (Q--) {
        int l, r;
        cin >> l >> r;

        int lnum = groupNum[l];
        int rnum = groupNum[r];

        int answer = 0;

        if (lnum + 1 <= rnum - 1)
            answer += dp[rnum - 1] - dp[lnum];

        if (lnum == rnum and S[l] != 'X')
            answer += (r - l + 1) / 2;
        else {
            if (S[l] != 'X')
                answer += (groupEnd[lnum] - l + 1) / 2;
            if (S[r] != 'X')
                answer += (r - groupStart[rnum] + 1) / 2;
        }

        cout << answer << '\n';
    }

    return 0;
}

Submission Info

Judge Result