This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
struct Node {
int sum, rems;
Node(): sum(0), rems(0) {}
Node(int v) {
if (v >= 0)
sum = v, rems = 0;
else
sum = 0, rems = 1;
}
Node(const Node &lnode, const Node &rnode) {
int delta = min(lnode.rems, rnode.sum);
rems = rnode.rems + lnode.rems - delta;
sum = lnode.sum + rnode.sum - delta;
}
};
template <int N, class AddableNode>
class SegmentTree {
private:
int n;
AddableNode st[4 * N];
inline void push_up(int id) {
st[id] = AddableNode(st[id << 1], st[id << 1 | 1]);
}
void update(int id, int l, int r, int i, int v) {
if (r < i or i < l)
return;
if (l == r) {
// cerr << "update " << i << ", v = " << v << endl;
st[id] = Node(v);
return;
}
int m = (l + r) >> 1;
update(id << 1, l, m, i, v);
update(id << 1 | 1, m + 1, r, i, v);
push_up(id);
}
AddableNode get(int id, int l, int r, int left, int right) {
if (r < left or right < l or right < left or r < l)
return AddableNode();
if (left <= l and r <= right)
return st[id];
int m = (l + r) >> 1;
return AddableNode(
get(id << 1, l, m, left, right),
get(id << 1 | 1, m + 1, r, left, right)
);
}
public:
inline void init(int _n) {
n = _n;
}
inline void update(int i, int v) { update(1, 1, n, i, v); }
inline AddableNode get(int left, int right) { return get(1, 1, n, left, right); }
};
const int MAX = 5e5 + 7;
int N, Q;
char str[MAX];
vector<pair<int, int>> queries_by_l[MAX];
void input() {
cin >> N >> (str + 1);
cin >> Q;
for (int q = 0; q < Q; q++) {
int l, r; cin >> l >> r;
queries_by_l[l].emplace_back(r, q);
}
}
SegmentTree<MAX, Node> st;
void init() {
st.init(N);
}
int ans[MAX];
void solve() {
deque<int> de;
for (int l = N; l >= 1; l--) {
if (str[l] == 'T') {
de.push_front(l);
}
else { // str[l] == 'C'
if (not de.empty()) {
int j = de.front();
de.pop_front();
// Add matched T
st.update(j, -1);
}
// Add C
st.update(l, +1);
}
for (const auto &query : queries_by_l[l]) {
int r, q;
tie(r, q) = query;
int cnt_T_in_deque = distance(
de.begin(),
upper_bound(de.begin(), de.end(), r)
);
int cnt_T_in_left_seq = st.get(l, r).rems;
// cerr << "[l, r] = [" << l << ", " << r << "]" << endl;
// cerr << "cnt_T_in_deque = " << cnt_T_in_deque << endl;
// cerr << "cnt_T_in_left_seq = " << cnt_T_in_left_seq << endl;
ans[q] = cnt_T_in_deque + cnt_T_in_left_seq;
}
}
for (int q = 0; q < Q; q++)
cout << ans[q] << '\n';
}
int main(void) {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
input();
init();
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |