#include <bits/stdc++.h>
using namespace std;
template<size_t t_N>
struct Segment_Tree{
struct Node{
int min_suffix, sum;
Node(){
min_suffix = 0;
sum = 0;
}
Node(int min_suffix, int sum){
this->min_suffix = min_suffix;
this->sum = sum;
}
friend Node merge(const Node &l, const Node &r){
Node answer;
answer.sum = l.sum + r.sum;
answer.min_suffix = min(r.min_suffix, l.min_suffix + r.sum);
return answer;
}
};
Node nodes[4 * t_N];
void update(int index, int l, int r, int s, int value){
if(s < l || r < s)
return;
if(l == r){
nodes[index] = {min(value, 0), value};
return;
}
int mid = (l + r) >> 1;
update(2 * index + 1, l, mid, s, value);
update(2 * index + 2, mid + 1, r, s, value);
nodes[index] = merge(nodes[2 * index + 1], nodes[2 * index + 2]);
}
Node query_node(int index, int l, int r, int sl, int sr){
if(sl > r || sr < l)
return {0, 0};
if(sl <= l && r <= sr)
return nodes[index];
int mid = (l + r) >> 1;
Node lvalue = query_node(2 * index + 1, l, mid, sl, sr);
Node rvalue = query_node(2 * index + 2, mid + 1, r, sl, sr);
return merge(lvalue, rvalue);
}
int query(int index, int l, int r, int sl, int sr){
return query_node(index, l, r, sl, sr).min_suffix;
}
};
const int mx_N = 5e5 + 3;
int n, q;
string s;
int a[mx_N];
vector<pair<int, int>> queries[mx_N];
Segment_Tree<mx_N> segment_tree;
int answer[mx_N];
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> s;
for(int i = 0; i < n; ++i)
a[i + 1] = (s[i] == 'C') ? 1 : -1;
cin >> q;
for(int i = 0; i < q; ++i){
int l, r;
cin >> l >> r;
queries[l].push_back({r, i});
}
for(int i = 1; i <= n; ++i)
segment_tree.update(0, 1, n, i, a[i]);
vector<int> st;
for(int i = n; i >= 1; --i){
if(a[i] == 1){
if(!st.empty()){
segment_tree.update(0, 1, n, st.back(), -1);
st.pop_back();
}
}
else{
segment_tree.update(0, 1, n, i, 0);
st.push_back(i);
}
for(auto pp: queries[i]){
int r = pp.first;
int index = pp.second;
answer[index] = -segment_tree.query(0, 1, n, i, r) + (upper_bound(st.rbegin(), st.rend(), r) - st.rbegin());
}
}
for(int i = 0; i < q; ++i)
cout << answer[i] << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
27776 KB |
Output is correct |
2 |
Correct |
21 ms |
27776 KB |
Output is correct |
3 |
Correct |
22 ms |
27776 KB |
Output is correct |
4 |
Correct |
24 ms |
27904 KB |
Output is correct |
5 |
Correct |
21 ms |
27776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
27776 KB |
Output is correct |
2 |
Correct |
21 ms |
27776 KB |
Output is correct |
3 |
Correct |
22 ms |
27776 KB |
Output is correct |
4 |
Correct |
24 ms |
27904 KB |
Output is correct |
5 |
Correct |
21 ms |
27776 KB |
Output is correct |
6 |
Correct |
89 ms |
30456 KB |
Output is correct |
7 |
Correct |
76 ms |
30584 KB |
Output is correct |
8 |
Correct |
88 ms |
30712 KB |
Output is correct |
9 |
Correct |
84 ms |
30968 KB |
Output is correct |
10 |
Correct |
102 ms |
30968 KB |
Output is correct |
11 |
Correct |
96 ms |
31308 KB |
Output is correct |
12 |
Correct |
91 ms |
31224 KB |
Output is correct |
13 |
Correct |
97 ms |
31352 KB |
Output is correct |
14 |
Correct |
87 ms |
31224 KB |
Output is correct |
15 |
Correct |
88 ms |
31096 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
27776 KB |
Output is correct |
2 |
Correct |
21 ms |
27776 KB |
Output is correct |
3 |
Correct |
22 ms |
27776 KB |
Output is correct |
4 |
Correct |
24 ms |
27904 KB |
Output is correct |
5 |
Correct |
21 ms |
27776 KB |
Output is correct |
6 |
Correct |
89 ms |
30456 KB |
Output is correct |
7 |
Correct |
76 ms |
30584 KB |
Output is correct |
8 |
Correct |
88 ms |
30712 KB |
Output is correct |
9 |
Correct |
84 ms |
30968 KB |
Output is correct |
10 |
Correct |
102 ms |
30968 KB |
Output is correct |
11 |
Correct |
96 ms |
31308 KB |
Output is correct |
12 |
Correct |
91 ms |
31224 KB |
Output is correct |
13 |
Correct |
97 ms |
31352 KB |
Output is correct |
14 |
Correct |
87 ms |
31224 KB |
Output is correct |
15 |
Correct |
88 ms |
31096 KB |
Output is correct |
16 |
Correct |
783 ms |
52376 KB |
Output is correct |
17 |
Correct |
511 ms |
48548 KB |
Output is correct |
18 |
Correct |
600 ms |
49544 KB |
Output is correct |
19 |
Correct |
614 ms |
51256 KB |
Output is correct |
20 |
Correct |
722 ms |
51724 KB |
Output is correct |
21 |
Correct |
798 ms |
54108 KB |
Output is correct |
22 |
Correct |
685 ms |
53424 KB |
Output is correct |
23 |
Correct |
797 ms |
54276 KB |
Output is correct |
24 |
Correct |
702 ms |
53560 KB |
Output is correct |
25 |
Correct |
684 ms |
53004 KB |
Output is correct |