oj.uz

Submission #60769

# Submission time Handle Problem Language Result Execution time Memory
60769 2018-07-24T16:24:59 Z SpaimaCarpatilor Election (BOI18_election) C++17
82 / 100
 3000 ms 89252 KB 
#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++)
    if (nxt[i][0] == 0)
        nxt[i][0] = N + 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 - min (mini, minSuf[pos][0]);
        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:59:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d", &M);
 ~~~~~~^~~~~~~~~~
election.cpp:63: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.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 760 KB Output is correct
2 Correct 5 ms 868 KB Output is correct
3 Correct 4 ms 868 KB Output is correct
4 Correct 5 ms 908 KB Output is correct
5 Correct 4 ms 924 KB Output is correct

Subtask #2
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 760 KB Output is correct
2 Correct 5 ms 868 KB Output is correct
3 Correct 4 ms 868 KB Output is correct
4 Correct 5 ms 908 KB Output is correct
5 Correct 4 ms 924 KB Output is correct
6 Correct 163 ms 12200 KB Output is correct
7 Correct 141 ms 12288 KB Output is correct
8 Correct 93 ms 12316 KB Output is correct
9 Correct 84 ms 12316 KB Output is correct
10 Correct 77 ms 12316 KB Output is correct
11 Correct 1572 ms 12624 KB Output is correct
12 Correct 71 ms 12624 KB Output is correct
13 Correct 72 ms 12624 KB Output is correct
14 Correct 66 ms 12624 KB Output is correct
15 Correct 67 ms 12624 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 760 KB Output is correct
2 Correct 5 ms 868 KB Output is correct
3 Correct 4 ms 868 KB Output is correct
4 Correct 5 ms 908 KB Output is correct
5 Correct 4 ms 924 KB Output is correct
6 Correct 163 ms 12200 KB Output is correct
7 Correct 141 ms 12288 KB Output is correct
8 Correct 93 ms 12316 KB Output is correct
9 Correct 84 ms 12316 KB Output is correct
10 Correct 77 ms 12316 KB Output is correct
11 Correct 1572 ms 12624 KB Output is correct
12 Correct 71 ms 12624 KB Output is correct
13 Correct 72 ms 12624 KB Output is correct
14 Correct 66 ms 12624 KB Output is correct
15 Correct 67 ms 12624 KB Output is correct
16 Correct 2356 ms 89252 KB Output is correct
17 Correct 674 ms 89252 KB Output is correct
18 Correct 1620 ms 89252 KB Output is correct
19 Correct 2027 ms 89252 KB Output is correct
20 Correct 824 ms 89252 KB Output is correct
21 Execution timed out 3051 ms 89252 KB Time limit exceeded
22 Halted 0 ms 0 KB -