// M
#include<bits/stdc++.h>
#define lc (id << 1)
#define rc (lc ^ 1)
#define md ((l + r) >> 1)
using namespace std;
const int N = 500005, MXS = N * 4;
int n, q, R[N];
//char A[N];
string A;
int LZ[MXS], MN[MXS];
vector < pair < int , int > > V[N];
inline void Shift(int id)
{
LZ[lc] += LZ[id];
MN[lc] += LZ[id];
LZ[rc] += LZ[id];
MN[rc] += LZ[id];
LZ[id] = 0;
}
void Add(int le, int ri, int val, int id = 1, int l = 0, int r = n + 1)
{
if (ri <= l || r <= le)
return ;
if (le <= l && r <= ri)
{
LZ[id] += val;
MN[id] += val;
return ;
}
Shift(id);
Add(le, ri, val, lc, l, md);;
Add(le, ri, val, rc, md, r);
MN[id] = min(MN[lc], MN[rc]);
}
int GetMin(int le, int ri, int id = 1, int l = 0, int r = n + 1)
{
if (ri <= l || r <= le)
return MXS;
if (le <= l && r <= ri)
return MN[id];
Shift(id);
return min(GetMin(le, ri, lc, l, md), GetMin(le, ri, rc, md, r));
}
int main()
{
//scanf("%d%s%d", &n, &A[1], &q);
cin >> n >> A >> q;
A = "#" + A;
for (int i = 1; i <= q; i ++)
{
int l, r;
//scanf("%d%d", &l, &r);
cin >> l >> r;
V[r].push_back({i, l});
}
vector < int > stk;
for (int i = 1; i <= n; i ++)
{
if (A[i] == 'C')
{
if (stk.size())
Add(stk.back(), n + 1, -1), stk.pop_back();
Add(i, n + 1, 1);
}
else
stk.push_back(i);
for (auto X : V[i])
R[X.first] = (int)stk.size() + max(-(GetMin(X.second, i + 1) - GetMin(X.second - 1, X.second)), 0);
}
for (int i = 1; i <= q; i ++)
printf("%d\n", R[i]);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
12160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
12160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
12160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
