//Giorgi Kldiashvili
#include <bits/stdc++.h>
#define ll long long
#define fr first
#define sc second
#define M 1000000007ll
using namespace std;
const int N = 500020;
char ch[N];
bool C[N];
int L[N], R[N], D[N];
int F[2 * N], answer[N];
int n, m;
int A, B;
int K[N];
vector < pair < int, int > > q[N];
int T[3 * N], t[3 * N];
void upd(int v, int x)
{
if(x == 1)
T[v] += t[v], t[v] = 0;
else
{
t[v + v] += t[v];
t[v + v + 1] += t[v];
t[v] = 0;
T[v] = max(T[v + v] + t[v + v], T[v + v + 1] + t[v + v + 1]);
}
}
void Build(int v, int tl, int tr)
{
if(tl == tr - 1)
{
T[v] = -R[tl];
return;
}
Build(v + v, tl, tl + tr >> 1);
Build(v + v + 1, tl + tr >> 1, tr);
T[v] = max(T[v + v], T[v + v + 1]);
}
void update(int v, int tl, int tr, int l, int val)
{
upd(v, tr - tl);
if(tr <= l) return;
if(l <= tl)
{
t[v] += val;
upd(v, tr - tl);
return;
}
update(v + v, tl, tl + tr >> 1, l, val);
update(v + v + 1, tl + tr >> 1, tr, l, val);
T[v] = max(T[v + v] + t[v + v], T[v + v + 1] + t[v + v + 1]);
}
int get(int v, int tl, int tr, int l, int r)
{
upd(v, tr - tl);
if(tr <= l || r <= tl) return 0;
if(l <= tl && tr <= r)
return T[v];
int x, y;
x = get(v + v, tl, tl + tr >> 1, l, r);
y = get(v + v + 1, tl + tr >> 1, tr, l, r);
return max(x, y);
}
int main()
{
scanf("%d\n", &n);
scanf("%s", &ch);
L[0] = 500002;
for(int i = 0; i < 3 * N; ++ i)
T[i] = -1e9;
for(int i = 1; i <= n; ++ i)
{
int x = (ch[i - 1] == 'C')?-1:1;
L[i] = L[i - 1] + x;
}
for(int i = n; i >= 1; -- i)
{
int x = (ch[i - 1] == 'C')?1:-1;
R[i] = R[i + 1] + x;
}
scanf("%d", &m);
for(int i = 1; i <= m; ++ i)
{
int x, y;
scanf("%d %d", &x, &y);
q[x].push_back(make_pair(y, i));
for(int j = x; j <= y; ++ j)
answer[i] = max(answer[i], L[j] - L[x - 1]);
}
for(int i = n; i >= 0; -- i)
{
D[i] = F[L[i] + 1];
F[L[i]] = i;
if(D[i] == 0) D[i] = n + 1;
}
Build(1, 1, n + 1);
int now = D[0];
while(now != n + 1)
{
update(1, 1, n + 1, now + 1, 1);
now = D[now];
}
now = 1;
for(int l = 1; l <= n; ++ l)
{
for(int i = 0; i < q[l].size(); ++ i)
answer[q[l][i].sc] = max(answer[q[l][i].sc], get(1, 1, n + 1, l, q[l][i].fr + 1) + R[q[l][i].fr + 1]);
if(l == n) break;
if(ch[l - 1] == 'T')
update(1, 1, n + 1, l + 1, -1);
else
update(1, 1, n + 1, D[l] + 1, 1);
}
for(int i = 1; i <= m; ++ i)
printf("%d\n", answer[i]);
}
Compilation message
election.cpp: In function 'void Build(int, int, int)':
election.cpp:44:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
Build(v + v, tl, tl + tr >> 1);
~~~^~~~
election.cpp:45:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
Build(v + v + 1, tl + tr >> 1, tr);
~~~^~~~
election.cpp: In function 'void update(int, int, int, int, int)':
election.cpp:59:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
update(v + v, tl, tl + tr >> 1, l, val);
~~~^~~~
election.cpp:60:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
update(v + v + 1, tl + tr >> 1, tr, l, val);
~~~^~~~
election.cpp: In function 'int get(int, int, int, int, int)':
election.cpp:71:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
x = get(v + v, tl, tl + tr >> 1, l, r);
~~~^~~~
election.cpp:72:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
y = get(v + v + 1, tl + tr >> 1, tr, l, r);
~~~^~~~
election.cpp: In function 'int main()':
election.cpp:79:18: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[500020]' [-Wformat=]
scanf("%s", &ch);
~~~^
election.cpp:119:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < q[l].size(); ++ i)
~~^~~~~~~~~~~~~
election.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d\n", &n);
~~~~~^~~~~~~~~~~~
election.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", &ch);
~~~~~^~~~~~~~~~~
election.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &m);
~~~~~^~~~~~~~~~
election.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
18040 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
18280 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
18040 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
18280 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
18040 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
18280 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
