oj.uz

답안 #53905

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
53905 2018-07-01T16:58:51 Z SpaimaCarpatilor Editor (BOI15_edi) C++17
63 / 100
 527 ms 305100 KB 
#include<bits/stdc++.h>

using namespace std;

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

const int maxN = 12000009;
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) 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

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.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 6 ms 2276 KB Output is correct
3 Correct 3 ms 2276 KB Output is correct
4 Correct 2 ms 2276 KB Output is correct
5 Correct 6 ms 2276 KB Output is correct
6 Correct 4 ms 2276 KB Output is correct
7 Correct 7 ms 2276 KB Output is correct
8 Correct 2 ms 2276 KB Output is correct
9 Correct 7 ms 2276 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 213 ms 79060 KB Output is correct
2 Correct 223 ms 79296 KB Output is correct

Subtask #3
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 192 ms 79296 KB Output is correct
2 Correct 191 ms 79296 KB Output is correct
3 Correct 220 ms 91316 KB Output is correct
4 Correct 229 ms 91316 KB Output is correct
5 Correct 348 ms 130456 KB Output is correct
6 Correct 191 ms 130456 KB Output is correct

Subtask #4
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 6 ms 2276 KB Output is correct
3 Correct 3 ms 2276 KB Output is correct
4 Correct 2 ms 2276 KB Output is correct
5 Correct 6 ms 2276 KB Output is correct
6 Correct 4 ms 2276 KB Output is correct
7 Correct 7 ms 2276 KB Output is correct
8 Correct 2 ms 2276 KB Output is correct
9 Correct 7 ms 2276 KB Output is correct
10 Correct 213 ms 79060 KB Output is correct
11 Correct 223 ms 79296 KB Output is correct
12 Correct 192 ms 79296 KB Output is correct
13 Correct 191 ms 79296 KB Output is correct
14 Correct 220 ms 91316 KB Output is correct
15 Correct 229 ms 91316 KB Output is correct
16 Correct 348 ms 130456 KB Output is correct
17 Correct 191 ms 130456 KB Output is correct
18 Runtime error 527 ms 305100 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -