Submission #75815969

---

Source Code Expand

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define rep(i, s, e) for (ll i = (s); i <= (e); i++)
#define all(v) v.begin(), v.end()
#define pb push_back
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using P = array<ll, 2>;
ll n, q, l, r;
string st;
struct T {
	ll cst, len, ld, rd;
	char lc, rc;
} seg[1212121];
T mg(T l, T r) {
	if (l.len == 0)
		return r;
	if (r.len == 0)
		return l;
	T rs;
	bool h = 0;
	rs.cst = l.cst + r.cst;
	rs.len = l.len + r.len;
	rs.lc = l.lc, rs.rc = r.rc;
	if (l.ld == l.len && l.lc == r.lc)
		rs.ld = l.ld + r.ld, h = 1;
	else
		rs.ld = l.ld;
	if (r.rd == r.len && l.rc == r.rc)
		rs.rd = l.rd + r.rd, h = 1;
	else
		rs.rd = r.rd;
	if (l.rd != l.len && r.ld != r.len && l.rc == r.lc) {
		if (l.rc != 'X')
			rs.cst += (l.rd + r.ld) / 2;
	} else if (!h) {
		if (l.rd != l.len && l.rc != 'X')
			rs.cst += l.rd / 2;
		if (r.ld != r.len && r.lc != 'X')
			rs.cst += r.ld / 2;
	}
	return rs;
}
void ini(ll s, ll e, ll d) {
	if (s < e) {
		ini(s, s + e >> 1, d * 2), ini(s + e + 2 >> 1, e, d * 2 + 1);
		seg[d] = mg(seg[d * 2], seg[d * 2 + 1]);
	} else {
		seg[d] = {0, 1, 1, 1, st[s - 1], st[s - 1]};
	}
}
T fnd(ll s, ll e, ll d) {
	if (s > r || e < l)
		return {0, 0, 0, 0, 0, 0};
	if (s >= l && e <= r)
		return seg[d];
	return mg(fnd(s, s + e >> 1, d * 2), fnd(s + e + 2 >> 1, e, d * 2 + 1));
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> q >> st;
	ini(1, n, 1);
	while (q--) {
		cin >> l >> r;
		T rs = fnd(1, n, 1);
		ll res = rs.cst;
		if (rs.lc != 'X')
			res += rs.ld / 2;
		if (rs.rc != 'X' && rs.rd != rs.len)
			res += rs.rd / 2;
		cout << res << '\n';
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function 'void ini(ll, ll, ll)':
./Main.cpp:48:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |                 ini(s, s + e >> 1, d * 2), ini(s + e + 2 >> 1, e, d * 2 + 1);
      |                        ~~^~~
./Main.cpp:48:54: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |                 ini(s, s + e >> 1, d * 2), ini(s + e + 2 >> 1, e, d * 2 + 1);
      |                                                ~~~~~~^~~
./Main.cpp: In function 'T fnd(ll, ll, ll)':
./Main.cpp:59:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |         return mg(fnd(s, s + e >> 1, d * 2), fnd(s + e + 2 >> 1, e, d * 2 + 1));
      |                          ~~^~~
./Main.cpp:59:56: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |         return mg(fnd(s, s + e >> 1, d * 2), fnd(s + e + 2 >> 1, e, d * 2 + 1));
      |                                                  ~~~~~~^~~

Judge Result