oj.uz

Submission #937860

# Submission time Handle Problem Language Result Execution time Memory
937860 2024-03-04T15:39:31 Z sleepntsheep Election (BOI18_election) C
28 / 100
 3000 ms 3320 KB 
#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

election.c: In function 'main':
election.c:27:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     scanf("%d%s%d", &n, s, &q);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~
election.c:34:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         scanf("%d%d", &x, &y);
      |         ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2396 KB Output is correct
2 Correct 8 ms 2396 KB Output is correct
3 Correct 6 ms 2540 KB Output is correct
4 Correct 7 ms 2396 KB Output is correct
5 Correct 5 ms 2392 KB Output is correct

Subtask #2
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2396 KB Output is correct
2 Correct 8 ms 2396 KB Output is correct
3 Correct 6 ms 2540 KB Output is correct
4 Correct 7 ms 2396 KB Output is correct
5 Correct 5 ms 2392 KB Output is correct
6 Execution timed out 3038 ms 3320 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2396 KB Output is correct
2 Correct 8 ms 2396 KB Output is correct
3 Correct 6 ms 2540 KB Output is correct
4 Correct 7 ms 2396 KB Output is correct
5 Correct 5 ms 2392 KB Output is correct
6 Execution timed out 3038 ms 3320 KB Time limit exceeded
7 Halted 0 ms 0 KB -