Submission #60773

#	Time	Username	Problem	Language	Result	Execution time	Memory
60773		SpaimaCarpatilor	Election (BOI18_election)	C++17	100 / 100	1779 ms	161140 KiB

election

#include<bits/stdc++.h>

using namespace std;

int N, M, getCount[500009][19], nxt[500009][19], 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]),
    getCount[i][0] = nxt[i][0] - (nxtS[i - 1] + 1);
for (int i=1; i<=N; i++)
    if (nxt[i][0] == 0)
        nxt[i][0] = N + 1;
for (int i=1; i<=lg[N]; i++)
    for (int j=1; j<=N; j++)
        nxt[j][i] = nxt[nxt[j][i - 1]][i - 1],
        minSuf[j][i] = min (minSuf[j][i - 1], minSuf[nxt[j][i - 1]][i - 1]),
        getCount[j][i] = getCount[j][i - 1] + getCount[nxt[j][i - 1]][i - 1];
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];
    for (int i=lg[R - pos + 1]; i>=0; i--)
        if (nxt[pos][i] != 0 && nxt[pos][i] <= R)
            mini = min (mini, minSuf[pos][i]),
            cnt += getCount[pos][i],
            pos = nxt[pos][i];
    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 - min (mini, minSuf[pos][0]);
    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:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d", &M);
 ~~~~~~^~~~~~~~~~
election.cpp:67: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: 28 / 28
• Subtask 2: 54 / 54
• Subtask 3: 18 / 18