This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//Pantyhose(black) + glasses = infinity
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"
const int INF = 1e9;
const int MAX_N = 500002;
class segment_tree {
public:
vector<pair<int, int> > st;
int n;
segment_tree(int _n) {
n = _n;
st.resize(4*n, make_pair(0, 0));
}
void down(int id) {
int tmp = st[id].second;
st[id].second = 0;
st[id*2].first += tmp;
st[id*2].second += tmp;
st[id*2+1].first += tmp;
st[id*2+1].second += tmp;
}
void upd(int u, int v, int val, int l, int r, int id) {
if (v<l || u>r)
return;
if (u<=l && r<=v) {
st[id].first += val;
st[id].second += val;
return;
}
int mid = (l + r) / 2;
down(id);
upd(u, v, val, l, mid, id*2);
upd(u, v, val, mid+1, r, id*2+1);
st[id].first = min(st[id*2].first, st[id*2+1].first);
}
int get(int u, int v, int l, int r, int id) {
if (v<l || u>r)
return INF;
if (u<=l && r<=v)
return st[id].first;
int mid = (l + r) / 2;
down(id);
return min(get(u, v, l, mid, id*2),
get(u, v, mid+1, r, id*2+1));
}
void upd(int u, int v, int val) {
upd(u, v, val, 1, n, 1);
}
int get(int u, int v) {
return get(u, v, 1, n, 1);
}
};
int n, nQueries, a[MAX_N], suff_sum[MAX_N], pref_sum[MAX_N], res[MAX_N];
vector<pair<int, int> > q[MAX_N];
string S;
void enter() {
cin >> n >> S >> nQueries;
S = '@' + S;
for (int i=1; i<=nQueries; ++i) {
int l, r;
cin >> l >> r;
q[l].push_back(make_pair(r, i));
}
}
void init() {
}
void solve() {
segment_tree tr(n);
for (int i=1; i<=n; ++i)
a[i] = S[i]=='T' ? -1 : 1;
for (int i=1; i<=n; ++i)
suff_sum[i] = suff_sum[i-1] + a[i];
for (int i=n; i>=1; --i) {
pref_sum[i] = pref_sum[i+1] + a[i];
tr.upd(i, i, pref_sum[i]);
}
vector<int> p;
for (int l=n; l>=1; --l) {
if (a[l]==-1) {
p.push_back(l);
tr.upd(1, l, 1);
//debug(tr.get(3, 8));
}
else {
while (p.size() && suff_sum[p.back()] - suff_sum[l-1] >= 0) {
tr.upd(1, p.back(), -1);
//debug(tr.get(3, 8));
p.pop_back();
}
}
for (int j=0; j<q[l].size(); ++j) {
int r = q[l][j].first;
//debug(tr.get(r+1, r+1));
if (r<n)
res[q[l][j].second] = max(0, -(tr.get(l, r) - tr.get(r+1, r+1)))
+ upper_bound(p.rbegin(), p.rend(), r) - p.rbegin();
else
res[q[l][j].second] = max(0, -tr.get(l, r)) +
upper_bound(p.rbegin(), p.rend(), r) - p.rbegin();
}
}
for (int i=1; i<=nQueries; ++i)
cout << res[i] << '\n';
}
int main() {
#ifdef GLASSES_GIRL
freopen(FILE_NAME".inp", "r", stdin);
freopen(FILE_NAME".out", "w", stdout);
#endif
ios::sync_with_stdio(0); cin.tie(0);
enter();
solve();
}
Compilation message (stderr)
election.cpp: In function 'void solve()':
election.cpp:109:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j=0; j<q[l].size(); ++j) {
~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |