Submission #37025190

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define chmax(x,y) x = max(x,y);
#define chmin(x,y) x = min(x,y);
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, -1, 0, 1};
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;
const double PI = acos(-1);



int main() {
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    string ns;
    char now = 'Z';
    vector<int> idx_asy(n);
    rep(i,n) {
        if (s[i] != now) {
            ns += s[i];
        }
        idx_asy[i] = ns.size()-1;
        now = s[i];
    }
    n = ns.size();
    vector<int> l(q), r(q);
    rep(i,q) {
        cin >> l[i] >> r[i];
        l[i]--; r[i]--;
        l[i] = idx_asy[l[i]];
        r[i] = idx_asy[r[i]];

        // cout << l[i] << " " << r[i] << endl;
    }
    vector<int> ans(q, INF);


    rep(i,q) {
        int num = r[i] - l[i] + 1;
        if (num == 1) ans[i] = 0;
        else if (ns[l[i]] == ns[r[i]]) {
            ans[i] = (num-2)/2 + 1;
        } else {
            ans[i] = (num-1)/2 + 1;
        }
    }


    rep(i,q) cout << ans[i] << endl;
    return 0;
}

Submission Info

Judge Result