#include<bits/stdc++.h>
using namespace std;
int N, M, nxt[500009][2], nxtS[500009], nextC[500009], s[500009], a[500009], maxS[19][500009], minSuf[500009][19], lg[500009], lst[1000009];
char sir[500009];
void buildRMQ ()
{
for (int i=1; i<=N; i++)
maxS[0][i] = s[i];
for (int i=2; i<=N; i++)
lg[i] = lg[i >> 1] + 1;
for (int i=1; i<=lg[N]; i++)
for (int j=1; j + (1 << i) - 1 <= N; j++)
maxS[i][j] = max (maxS[i - 1][j], maxS[i - 1][j + (1 << (i - 1))]);
}
int getMinSuf (int i, int j)
{
int p = lg[j - i + 1];
///s[j] - max (s[i - 1 <= p <= j])
int curr = max (max (maxS[p][i], maxS[p][j - (1 << p) + 1]), s[i - 1]);
return s[j] - curr;
}
int getS (int i, int j)
{
return s[j] - s[i - 1];
}
int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);
scanf ("%d\n", &N);
scanf ("%s", sir + 1);
for (int i=1; i<=N; i++)
a[i] = (sir[i] == 'C' ? +1 : -1),
s[i] = s[i - 1] + a[i];
buildRMQ ();
for (int i=N; i>=1; i--)
if (sir[i] == 'C') nextC[i] = i;
else nextC[i] = nextC[i + 1];
for (int i=N; i>=0; i--)
nxtS[i] = lst[s[i] + N],
lst[s[i] + N] = i;
for (int i=1; i<=N; i++)
if (nxtS[i - 1] == 0) nxt[i][0] = N + 1;
else
nxt[i][0] = nextC[nxtS[i - 1] + 1],
minSuf[i][0] = getMinSuf (i, nxtS[i - 1]);
/*for (int i=1; i<=N; i++)
printf ("%d%c", nxt[i][0], " \n"[i == N]);*/
scanf ("%d", &M);
while (M --)
{
int L, R;
scanf ("%d %d", &L, &R);
if (nextC[L] == 0 || nextC[L] > R)
{
printf ("%d\n", R - L + 1);
continue;
}
int mini = 0, ans = 0, cnt = nextC[L] - L, pos = nextC[L];
while (1)
{
if (nxt[pos][0] <= R)
{
cnt += nxt[pos][0] - (nxtS[pos - 1] + 1);
mini = min (mini, minSuf[pos][0]), pos = nxt[pos][0];
continue;
}
if (nxtS[pos - 1] == 0 || nxtS[pos - 1] >= R)
ans = cnt - min (getMinSuf (pos, R), mini + getS (pos, R));
else
ans = R - nxtS[pos - 1] + cnt - mini;
break;
}
printf ("%d\n", ans);
}
return 0;
}
Compilation message
election.cpp: In function 'int main()':
election.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d\n", &N);
~~~~~~^~~~~~~~~~~~
election.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%s", sir + 1);
~~~~~~^~~~~~~~~~~~~~~
election.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &M);
~~~~~~^~~~~~~~~~
election.cpp:60:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d %d", &L, &R);
~~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
