# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
937860 | sleepntsheep | Election (BOI18_election) | C11 | 3038 ms | 3320 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<stdio.h>
int lo(int a, int b)
{
return a<b?a:b;
}
int hi(int a, int b)
{
return a>b?a:b;
}
#define N 500000
int n, q;
char s[N+1];
int go[N],bk[N];
int f(char c)
{
return c == 'C' ? 1 : -1;
}
int main()
{
scanf("%d%s%d", &n, s, &q);
go[0] = f(s[0]);
bk[n-1] = f(s[n-1]);
for (int i = 1; i < n; ++i) go[i] = go[i-1] + f(s[i]);
for (int i = n - 2; i >= 0; --i) bk[i] = bk[i+1] + f(s[i]);
for (int x, y, i = 0; i < q; ++i)
{
scanf("%d%d", &x, &y);
--y; --x;
int c = 0, L = 0, R = 0;
int at[4000]={0},m=0;
for (int i = x; i <= y; ++i)
if (s[i] == 'C')
++c;
else
{
if (!c) ++L, at[m++] = i;
else --c;
}
int tot = 0;
for (int i = at[0]; i <= y; ++i) tot += (s[i] == 'T');
c = 0;
for (int i = y; i >= x; --i)
{
if (s[i] == 'C') ++c;
else
{
if (i >= at[0])
{
if (m > 0 && tot && i == at[m-1])
{
--m;
++R;
--tot;
}
else
{
if (c) --c;
else ++R, --tot;
}
}
else
{
if (c) --c;
else ++R;
}
}
}
int z = hi(L, R);
printf("%d\n", z);
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |