Submission #60754

#	Time	Username	Problem	Language	Result	Execution time	Memory
60754		SpaimaCarpatilor	Election (BOI18_election)	C++17	0 / 100	7 ms	1144 KiB

election

#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[19][500009], 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 (stderr)

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);
     ~~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 28
• Subtask 2: 0 / 54
• Subtask 3: 0 / 18