#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
const int INF = 1e9 + 7, N = 500005;
int n;
string s;
struct node {
int ans, l, r, s;
node(char c = 'C') {
if(c == 'C') l = r = 0, ans = s = -1;
else ans = l = r = s = 1;
}
node operator + (node t) {
node res;
res.s = s + t.s;
res.l = max(l, s + t.l);
res.r = max(r + t.s, t.r);
res.ans = max({l + t.r, s + t.ans, t.s + ans});
return res;
}
} t[N * 4];
void build(int v = 1, int tl = 0, int tr = n) {
if(tr - tl == 1) {
t[v] = node(s[tl]);
return;
}
int tm = (tl + tr) / 2;
build(v * 2, tl, tm);
build(v * 2 + 1, tm, tr);
t[v] = t[v * 2] + t[v * 2 + 1];
}
node qry(int l, int r, int v = 1, int tl = 0, int tr = n) {
if(l <= tl && tr <= r) return t[v];
int tm = (tl + tr) / 2;
if(r <= tm) return qry(l, r, v * 2, tl, tm);
else if(l >= tm) return qry(l, r, v * 2 + 1, tm, tr);
else return qry(l, r, v * 2, tl, tm) + qry(l, r, v * 2 + 1, tm, tr);
}
signed main()
{
IO_OP;
cin >> n >> s;
build();
int q;
cin >> q;
while(q--) {
int l, r;
cin >> l >> r;
l--;
cout << qry(l, r).ans << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
31724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
31724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
31724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
