#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 n;
int a[500009];
struct node{
int minl, minli, minr, minri, rid, sum, tl, tr;
};
void print(node a){
cout << a.minl << " " << a.minli << " " << a.minr << " " << a.minri << "\n";
}
node tree[2000009];
node merge(node a, node b){
//print(a);print(b);
if(b.minl == 1e9)
return a;
if(a.minl == 1e9)
return b;
node ret;
a.minr += b.sum;
b.minl += a.sum;
if(b.minli == b.tl)
b.minli = a.rid;
ret.sum = a.sum+b.sum;
if(b.rid == b.tl)
ret.rid = a.rid;
else
ret.rid = b.rid;
ret.tl = a.tl;
if(a.minl < b.minl){
ret.minl = a.minl;
ret.minli = a.minli;
}
else if(a.minl > b.minl){
ret.minl = b.minl;
ret.minli = b.minli;
}
else{
ret.minl = a.minl;
ret.minli = min(a.minli, b.minli);
}
if(a.minr < b.minr){
ret.minr = a.minr;
ret.minri = a.minri;
}
else if(a.minr > b.minr){
ret.minr = b.minr;
ret.minri = b.minri;
}
else{
ret.minr = a.minr;
ret.minri = max(a.minri, b.minri);
}
//print(ret); cout << "-----------------\n";
return ret;
}
void build(int v, int tl, int tr){
if(tl > tr)
return;
if(tl == tr){
tree[v].minl = tree[v].minr = a[tl];
tree[v].minli = tree[v].minri = tl;
if(a[tl] < 0)
tree[v].rid = tl;
else
tree[v].rid = tl+1;
tree[v].sum = a[tl];
tree[v].tl = tl;
//cout << tl << "\n";
//print(tree[v]);
}
else{
int tm = (tl+tr)/2;
build(2*v, tl, tm);
build(2*v+1, tm+1, tr);
tree[v] = merge(tree[2*v], tree[2*v+1]);
//cout << tl << " " << tr << "\n";
//print(tree[v]);
}
}
node get(int v, int tl, int tr, int l, int r){
if(tl > r || tr < l)
return {(int)1e9};
else if(tl >= l && tr <= r)
return tree[v];
else{
int tm = (tl+tr)/2;
node node1 = get(2*v, tl, tm, l, r);
node node2 = get(2*v+1, tm+1, tr, l, r);
return merge(node1, node2);
}
}
int gor[500009];
int gol[500009];
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 = 0; i < n; ++i)
a[i] = input();
for(int i = 1; i < n; ++i){
if(a[i] > 0)
gol[i] = i;
else
gol[i] = gol[i-1];
}
gor[n-1] = n-1;
for(int i = n-2; i >= 0; --i){
if(a[i] > 0)
gor[i] = i;
else
gor[i] = gor[i+1];
}
build(1, 0, n-1);
//print(tree[1]);
int q;
cin >> q;
while(q--){
int l, r;
cin >> l >> r;
--l, --r;
int l1 = gor[l];
int r1 = gol[r];
if(l1 > r1){
cout << (r-l+1) << "\n";
continue;
}
int add = l1-l + r-r1;
node cur = get(1, 0, n-1, l1, r1);
if(cur.minli == cur.minri)
cout << add+max(0, max(-cur.minl, -cur.minr)) << "\n";
else
cout << add+max(0, -cur.minl)+max(0, -cur.minr) << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
