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"
#define endl '\n'
using namespace std;
void solve() {
int n;
string s;
cin >> n >> s;
int Q;
cin >> Q;
while(Q--) {
int l, r;
cin >> l >> r;
--l;
const int len = r - l;
string tmp = s.substr(l, len);
int ans = 0, balance = 0;
for(int i = 0; i < len; ++i) {
assert(balance >= 0);
if(tmp[i] == 'C') {
balance++;
continue;
}
assert(tmp[i] == 'T');
if(balance == 0) {
tmp[i] = 'X';
++ans;
}
else {
balance--;
}
}
reverse(tmp.begin(), tmp.end());
balance = 0;
for(int i = 0; i < len; ++i) {
assert(balance >= 0);
if(tmp[i] == 'C') {
balance++;
continue;
}
else if(tmp[i] == 'X') {
continue;
}
assert(tmp[i] == 'T');
if(balance == 0) {
tmp[i] = 'X';
++ans;
}
else {
balance--;
}
}
cout << ans << endl;
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// signed t; cin >> t; while(t--)
solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |