//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
//#pragma GCC target("bmi,bmi2,popcnt,lzcnt")
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cmath>
#include <fstream>
#include <climits>
#include <queue>
#include <algorithm>
#include <stdint.h>
#include <stack>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <cstring> // Для memset
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pii;
typedef pair <ld, ld> pdd;
const ll DIM = 700007;
const ll MXMASK = (1 << 21);
const ll INF = 1e18;
const ll mod = 998244353;
const ld eps = 0.00000000001;
const ld gr = (sqrt(5) + 1) / 2;
const ll offset = 10000;
const ll Bits = 20;
const ll dx[4] = { 1, 0, -1, 0 };
const ll dy[4] = { 0, 1, 0, -1 };
FILE* stream;
ll n, q;
string s;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//freopen_s(&stream, "input.txt", "r", stdin);
//freopen_s(&stream, "output.txt", "w", stdout);
cin >> n;
cin >> s;
cin >> q;
for (int i = 1; i <= q; i++) {
ll L, R;
deque < pair < char, ll > > d;
cin >> L >> R;
ll tc = 0;
for (int j = L - 1; j < R; j++) {
if (d.empty()) {
d.push_back({ s[j], 1 });
}
else if (d.back().first == s[j]) d.back().second++;
else d.push_back({ s[j], 1 });
if (s[j] == 'T') tc++;
}
ll res = 0, del = 0;
while (del < tc) {
if (d.size() == 1) {
if (d.front().first == 'T') res += d.front().second;
break;
}
else if (d.front().first == 'T') {
while (del < tc && d.front().second > 0) {
del++;
res++;
d.front().second--;
}
d.pop_front();
}
else if (d.back().first == 'T') {
while (del < tc && d.back().second > 0) {
del++;
res++;
d.back().second--;
}
d.pop_back();
}
else {
del += (d.front().second, d.back().second);
if (d.front().second == d.back().second) {
d.pop_front();
d.pop_back();
}
else if (d.front().second < d.back().second) d.pop_front();
else d.pop_back();
}
}
cout << res << endl;
}
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... |