Submission #75818141

---

Source Code Expand

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define int long long
using namespace std;

string S;
array<vector<array<int, 2>>, 303030> A;
array<int, 303030> L, R, F, ans;
int N, Q;

void update(int idx, int val) {
	for (; idx <= N; F[idx] += val, idx += idx & -idx);
}

int sum(int idx) {
	int res = 0;
	for (; idx; res += F[idx], idx -= idx & -idx);
	return res;
}

signed main() {
	cin >> N >> Q;
	cin >> S;
	S = '#' + S + '#';

	for (int i = 1; i <= N; i++) {
		L[i] = i;

		if (S[i] != 'X' && S[i] == S[i - 1]) {
			L[i] = L[i - 1];
		}
	}

	for (int i = N; i; i--) {
		R[i] = i;
		
		if (S[i] != 'X' && S[i] == S[i + 1]) {
			R[i] = R[i + 1];
		}
	}

	for (int i = 0; i < Q; i++) {
		int l, r;
		cin >> l >> r;
		A[r].push_back({i, l});
	}

	for (int r = 1; r <= N; r++) {
		if (R[r] == r) {
			update(L[r], r - L[r] + 1 >> 1);
		}

		for (auto [idx, l] : A[r]) {
			if (R[l] >= r) {
				ans[idx] = r - l + 1 >> 1;

				continue;
			}

			ans[idx] = sum(r) - sum(l - 1) + (R[r] > r) * (r - L[r] + 1 >> 1) + (L[l] < l) * (R[l] - l + 1 >> 1);
		}
	}

	for (int i = 0; i < Q; i++) {
		cout << ans[i] << '\n';
	}

	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function 'int main()':
./Main.cpp:50:47: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |                         update(L[r], r - L[r] + 1 >> 1);
      |                                      ~~~~~~~~~^~~
./Main.cpp:55:50: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |                                 ans[idx] = r - l + 1 >> 1;
      |                                            ~~~~~~^~~
./Main.cpp:60:81: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |                         ans[idx] = sum(r) - sum(l - 1) + (R[r] > r) * (r - L[r] + 1 >> 1) + (L[l] < l) * (R[l] - l + 1 >> 1);
      |                                                                        ~~~~~~~~~^~~
./Main.cpp:60:116: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |                         ans[idx] = sum(r) - sum(l - 1) + (R[r] > r) * (r - L[r] + 1 >> 1) + (L[l] < l) * (R[l] - l + 1 >> 1);

Judge Result