Submission #53906

#	Time	Username	Problem	Language	Result	Execution time	Memory
53906		SpaimaCarpatilor	Editor (BOI15_edi)	C++17	100 / 100	350 ms	118308 KiB

edi

#include<bits/stdc++.h>

using namespace std;

int N, a[300009], t[300009];
bool active[300009];

const int maxN = 15000009;
int nodes = 1, aint[maxN], l[maxN], r[maxN];
void build (int nod, int st, int dr)
{
    aint[nod] = 0;
    if (st == dr) return ;
    int mij = (st + dr) >> 1;
    l[nod] = ++nodes, build (l[nod], st, mij);
    r[nod] = ++nodes, build (r[nod], mij + 1, dr);
}

void split (int nod)
{
    if (l[nod] == 0)
        l[nod] = ++nodes;
    if (r[nod] == 0)
        r[nod] = ++nodes;
    if (aint[nod] > 0)
        aint[l[nod]] = aint[r[nod]] = aint[nod],
        aint[nod] = 0;
}

int change (int nod, int st, int dr, int x, int y, int newVal)
{
    if (x <= st && dr <= y)
    {
        aint[++nodes] = newVal;
        return nodes;
    }
    int mij = (st + dr) >> 1, curr = ++nodes;
    split (nod);
    if (x <= mij) l[curr] = change (l[nod], st, mij, x, y, newVal);
    else l[curr] = l[nod];
    if (mij < y) r[curr] = change (r[nod], mij + 1, dr, x, y, newVal);
    else r[curr] = r[nod];
    return curr;
}

int getPos (int nod, int st, int dr, int pos)
{
    if (st == dr || aint[nod] > 0) return aint[nod];
    int mij = (st + dr) >> 1;
    split (nod);
    if (pos <= mij) return getPos (l[nod], st, mij, pos);
    return getPos (r[nod], mij + 1, dr, pos);
}

void print (int nod, int st, int dr)
{
    if (st == dr)
    {
        if (st == 1) printf ("[");
        printf ("%d ", aint[nod]);
        if (dr == N) printf ("]\n");
        return ;
    }
    int mij = (st + dr) >> 1;
    split (nod);
    print (l[nod], st, mij);
    print (r[nod], mij + 1, dr);
}

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

scanf ("%d", &N);
build (1, 1, N), r[0] = 1;
for (int i=1; i<=N; i++)
{
    scanf ("%d", &a[i]);
    if (a[i] < 0)
    {
        int deg = -a[i], K = getPos (r[i - 1], 1, N, deg);
        if (!S.empty () && K < (*S.rbegin ())) t[i] = *S.rbegin (), K = i;
        else t[i] = t[K];
        r[i] = change (r[K - 1], 1, N, deg + 1, N, i);
        if (active[t[i]]) S.erase (t[i]), active[t[i]] = 0;
        else active[t[i]] = 1, S.insert (t[i]);
    }
    else r[i] = r[i - 1], S.insert (i), active[i] = 1;
    //print (r[i], 1, N);
    if (!S.empty ()) printf ("%d\n", a[*S.rbegin ()]);
    else printf ("0\n");
}

return 0;
}

Compilation message (stderr)

edi.cpp: In function 'int main()':
edi.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf ("%d", &N);
 ~~~~~~^~~~~~~~~~
edi.cpp:80:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ("%d", &a[i]);
     ~~~~~~^~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 15 / 15
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37