#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
const int N = 500'010;
struct node {
int mnl, mnr, mns;
} seg[N*4];
string s;
int pre[N], suf[N];
int n;
node merge(node x, node y)
{
node ans;
ans.mnl = min(x.mnl, y.mnl);
ans.mnr = min(x.mnr, y.mnr);
ans.mns = min({x.mns, y.mns, x.mnl + y.mnr});
return ans;
}
void build(int i, int b, int e)
{
if (e-b == 1) {
seg[i].mnl = pre[b];
seg[i].mnr = suf[b];
seg[i].mns = seg[i].mnl + seg[i].mnr;
return;
}
build(2*i+1, b, (b+e)/2);
build(2*i+2, (b+e)/2, e);
seg[i] = merge(seg[2*i+1], seg[2*i+2]);
}
node get(int l, int r, int i, int b, int e)
{
if (l <= b && e <= r)
return seg[i];
int mid = (b+e)/2;
if (l < mid && mid < r) {
return merge(get(l, r, 2*i+1, b, mid),
get(l, r, 2*i+2, mid, e));
} else if (l < mid) {
return get(l, r, 2*i+1, b, mid);
} else if (mid < r) {
return get(l, r, 2*i+2, mid, e);
} else {
for (;;)
cerr << "666\n";
*(int *)666 = 666;
return node{666, 666, 666};
// >:)
}
}
int main()
{
cin.tie(0) -> sync_with_stdio(false);
int q;
cin >> n;
cin >> s;
Loop (i,0,n)
pre[i+1] = pre[i] + (s[i] == 'C'? 1: -1);
LoopR (i,0,n)
suf[i] = suf[i+1] + (s[i] == 'C'? 1: -1);
build(0, 0, n+1);
cin >> q;
while (q--) {
int l, r;
cin >> l >> r;
--l;
auto ans = get(l, r+1, 0, 0, n+1);
cout << -(ans.mns - pre[l] - suf[r]) << '\n';
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
2 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
2 ms |
340 KB |
Output is correct |
6 |
Correct |
44 ms |
4308 KB |
Output is correct |
7 |
Correct |
45 ms |
4312 KB |
Output is correct |
8 |
Correct |
45 ms |
4436 KB |
Output is correct |
9 |
Correct |
35 ms |
4300 KB |
Output is correct |
10 |
Correct |
42 ms |
4260 KB |
Output is correct |
11 |
Correct |
42 ms |
4396 KB |
Output is correct |
12 |
Correct |
41 ms |
4404 KB |
Output is correct |
13 |
Correct |
41 ms |
4480 KB |
Output is correct |
14 |
Correct |
41 ms |
4384 KB |
Output is correct |
15 |
Correct |
46 ms |
4512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
2 ms |
340 KB |
Output is correct |
6 |
Correct |
44 ms |
4308 KB |
Output is correct |
7 |
Correct |
45 ms |
4312 KB |
Output is correct |
8 |
Correct |
45 ms |
4436 KB |
Output is correct |
9 |
Correct |
35 ms |
4300 KB |
Output is correct |
10 |
Correct |
42 ms |
4260 KB |
Output is correct |
11 |
Correct |
42 ms |
4396 KB |
Output is correct |
12 |
Correct |
41 ms |
4404 KB |
Output is correct |
13 |
Correct |
41 ms |
4480 KB |
Output is correct |
14 |
Correct |
41 ms |
4384 KB |
Output is correct |
15 |
Correct |
46 ms |
4512 KB |
Output is correct |
16 |
Correct |
426 ms |
19068 KB |
Output is correct |
17 |
Correct |
355 ms |
19136 KB |
Output is correct |
18 |
Correct |
375 ms |
19040 KB |
Output is correct |
19 |
Correct |
308 ms |
18640 KB |
Output is correct |
20 |
Correct |
400 ms |
18144 KB |
Output is correct |
21 |
Correct |
431 ms |
20072 KB |
Output is correct |
22 |
Correct |
428 ms |
19876 KB |
Output is correct |
23 |
Correct |
427 ms |
20064 KB |
Output is correct |
24 |
Correct |
423 ms |
19672 KB |
Output is correct |
25 |
Correct |
417 ms |
19388 KB |
Output is correct |