Submission #50964

#	Time	Username	Problem	Language	Result	Execution time	Memory
50964		SpaimaCarpatilor	Cake (CEOI14_cake)	C++17	100 / 100	359 ms	91352 KiB

cake

#include<bits/stdc++.h>

using namespace std;

int splitPos, N, M, a[250009], stk[2][250009], sz[2];

int last, initInv[250009], nxt[250009], prv[250009];
void read ()
{
    scanf ("%d %d", &N, &splitPos), M = N;
    for (int i=1; i<=N; i++)
        scanf ("%d", &a[i]), initInv[a[i]] = i;
    for (int i=0; i<=N + 1; i++)
    {
        if (i > 0) prv[initInv[i]] = initInv[i - 1];
        if (i <= N) nxt[initInv[i]] = initInv[i + 1];
    }
    last = initInv[N];
}

void del (int pos)
{
    if (pos == 0) prv[nxt[pos]] = 0;
    else
    {
        int x = prv[pos], y = nxt[pos];
        nxt[x] = y, prv[y] = x;
    }
}

void change (int P, int e)
{
    del (P);
    if (e == 1)
    {
        nxt[last] = P, prv[P] = last;
        a[P] = a[last] + 1, last = P;
        return ;
    }
    for (int i=last; e > 1; i = prv[i], e --)
        a[i] ++, nxt[P] = i;
    prv[P] = prv[nxt[P]];
    nxt[prv[P]] = P;
    prv[nxt[P]] = P;
    a[P] = a[nxt[P]] - 1;
}

void buildStacks ()
{
    for (int lin = 0; lin < 2; lin ++)
    {
        int bg = splitPos - 1, nd = 0, rat = -1;
        if (lin == 1)
            bg = splitPos + 1, nd = N + 1, rat = +1;
        for (int i=bg; i != nd; i+=rat)
            if (sz[lin] == 0 || a[stk[lin][sz[lin]]] < a[i])
                stk[lin][++sz[lin]] = i;
    }
}

void updateStack (int pos)
{
    int lin = 0;
    vector < int > currPos;
    if (pos < splitPos)
    {
        while (sz[0] > 0 && stk[0][sz[0]] <= pos)
            currPos.push_back (stk[0][sz[0] --]);
    }
    else
    {
        lin = 1;
        while (sz[1] > 0 && stk[1][sz[1]] >= pos)
            currPos.push_back (stk[1][sz[1] --]);
    }
    currPos.push_back (pos);
    reverse (currPos.begin (), currPos.end ());
    for (auto i : currPos)
        if (sz[lin] == 0 || a[stk[lin][sz[lin]]] < a[i])
            stk[lin][++sz[lin]] = i;
}

int countSmaller (int lin, int val)
{
    int p = 1, u = sz[lin], mij, ras = (lin == 0 ? 0 : N + 1);
    while (p <= u)
    {
        mij = (p + u) >> 1;
        if (a[stk[lin][mij]] >= val) ras = stk[lin][mij], u = mij - 1;
        else p = mij + 1;
    }
    if (lin == 1) ras = ras - splitPos - 1;
    else ras = splitPos - ras - 1;
    return ras;
}

int query (int pos)
{
    if (pos == splitPos) return 0;
    if (pos > splitPos)
    {
        int p = 2, u = sz[1], mij, ras = 1;
        while (p <= u)
        {
            mij = (p + u) >> 1;
            if (stk[1][mij] <= pos) ras = mij, p = mij + 1;
            else u = mij - 1;
        }
        return pos - splitPos + countSmaller (0, a[stk[1][ras]]);
    }
    int p = 2, u = sz[0], mij, ras = 1;
    while (p <= u)
    {
        mij = (p + u) >> 1;
        if (stk[0][mij] >= pos) ras = mij, p = mij + 1;
        else u = mij - 1;
    }
    return splitPos - pos + countSmaller (1, a[stk[0][ras]]);
}

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

read ();
buildStacks ();
int Q;
scanf ("%d\n", &Q);
while (Q --)
{
    char type;
    scanf ("%c ", &type);
    if (type == 'E')
    {
        int p, e;
        scanf ("%d %d\n", &p, &e);
        change (p, e);
        if (p != splitPos)
            updateStack (p);
        continue;
    }
    int pos;
    scanf ("%d\n", &pos);
    printf ("%d\n", query (pos));
}

return 0;
}

Compilation message (stderr)

cake.cpp: In function 'void read()':
cake.cpp:10:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d %d", &N, &splitPos), M = N;
     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
cake.cpp:12:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d", &a[i]), initInv[a[i]] = i;
         ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
cake.cpp: In function 'int main()':
cake.cpp:129:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d\n", &Q);
 ~~~~~~^~~~~~~~~~~~
cake.cpp:133:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%c ", &type);
     ~~~~~~^~~~~~~~~~~~~~
cake.cpp:137:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ("%d %d\n", &p, &e);
         ~~~~~~^~~~~~~~~~~~~~~~~~~
cake.cpp:144:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d\n", &pos);
     ~~~~~~^~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50