#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
int input(){
char c;
cin >> c;
if(c == 'T')
return -1;
else
return 1;
}
int a[1000009];
int pre[1000009];
int suf[1000009];
vector<int> lef[1000009];
vector<int> rig[1000009];
vector<int> v;
int treepre[2000009];
void buildpre(int v, int tl, int tr){
if(tl > tr)
return;
if(tl == tr){
treepre[v] = pre[tl];
}
else{
int tm = (tl+tr)/2;
buildpre(2*v, tl, tm);
buildpre(2*v+1, tm+1, tr);
treepre[v] = min(treepre[2*v], treepre[2*v+1]);
}
}
int getpre(int v, int tl, int tr, int l, int r){
if(tl > r || tr < l)
return 1e9;
else if(tl >= l && tr <= r)
return treepre[v];
else{
int tm = (tl+tr)/2;
return min(getpre(2*v, tl, tm, l, r),
getpre(2*v+1, tm+1, tr, l, r));
}
}
int treesuf[2000009];
void buildsuf(int v, int tl, int tr){
if(tl > tr)
return;
if(tl == tr){
treesuf[v] = suf[tl];
}
else{
int tm = (tl+tr)/2;
buildsuf(2*v, tl, tm);
buildsuf(2*v+1, tm+1, tr);
treesuf[v] = min(treesuf[2*v], treesuf[2*v+1]);
}
}
int getsuf(int v, int tl, int tr, int l, int r){
if(tl > r || tr < l)
return 1e9;
else if(tl >= l && tr <= r)
return treesuf[v];
else{
int tm = (tl+tr)/2;
return min(getsuf(2*v, tl, tm, l, r),
getsuf(2*v+1, tm+1, tr, l, r));
}
}
int n;
int add = 500001;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
cin >> n;
for(int i = 1; i <= n; ++i){
a[i] = input();
if(a[i] < 0)
v.pb(i);
}
for(int i = 1; i <= n; ++i){
pre[i] = pre[i-1]+a[i];
lef[pre[i]+add].pb(i);
}
for(int i = n; i > 0; --i){
suf[i] = suf[i+1] + a[i];
rig[suf[i]+add].pb(i);
}
for(int i = n; i > 0; --i)
sort(rig[suf[i]+add].begin(), rig[suf[i]+add].end());
buildpre(1, 1, n);
buildsuf(1, 1, n);
int q;
cin >> q;
while(q--){
int l, r;
cin >> l >> r;
int mini1 = getpre(1, 1, n, l, r)-pre[l-1];
int mini2 = getsuf(1, 1, n, l, r)-suf[r+1];
if(mini1 >= 0 && mini2 >= 0){
cout << "0\n";
continue;
}
else if(mini1 >= 0){
cout << -mini2 << "\n";
continue;
}
else if(mini2 >= 0){
cout << -mini1 << "\n";
continue;
}
mini1 *= -1;
mini2 *= -1;
int idx1, idx2;
if(a[l] == -1)
idx1 = l;
else{
idx1 = *lower_bound(lef[add+pre[l-1]-1].begin(), lef[add+pre[l-1]-1].begin(), l);
}
if(a[r] == -1)
idx2 = r;
else
idx2 = *(upper_bound(rig[add+suf[r+1]-1].begin(), rig[add+suf[r+1]-1].end(), r)-1);
int l1 = lower_bound(v.begin(), v.end(), idx1)-v.begin();
int r1 = lower_bound(v.begin(), v.end(), idx2)-v.begin();
if(l1 >= r1){
cout << max(mini1, mini2) << "\n";
continue;
}
int ans = mini1+mini2;
if(l1+mini1-1 >= r1-mini2+1)
ans -= (l1+mini1-1)-(r1-mini2+1)+1;
cout << ans << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
47480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
47480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
47480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
