oj.uz

Submission #43048

# Submission time Handle Problem Language Result Execution time Memory
43048 2018-03-08T09:28:42 Z PowerOfNinjaGo Editor (BOI15_edi) C++14
100 / 100
 1116 ms 208588 KB 
//Power Of Ninja Go
#include <bits/stdc++.h>
//#ifdef atom #else #endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii;
#define X first
#define Y second
#define vi vector<int>
#define vii vector< ii >
#define pb push_back
int n;
struct node
{
    int v;
    node *left, *right;
    node(int _v, node *a, node *b)
    {
        v = _v;
        left = a; right = b;
    }
    node *insert(int x, int dx, int L = 0, int R = n)
    {
        if(L<= x && x<= R)
        {
            if(L == R) return new node(dx, NULL, NULL);
            int M = (L+R)/2;
            node *ret = new node(0, left->insert(x, dx, L, M), right->insert(x, dx, M+1, R));
            ret->v = max(ret->left->v, ret->right->v);
            //printf("L R is %d\n", ret->v);
            return ret;
        }
        return this;
    }
    int ask(int i, int j, int L = 0, int R = n)
    {
        if(i> R || j< L) return 0;
        if(i<= L && R<= j) return v;
        int M = (L+R)/2;
        int x = left->ask(i, j, L, M);
        int y = right->ask(i, j, M+1, R);
        return max(x, y);
    }
};
const int maxn = 3e5+5;
node *root[maxn];
int num[maxn];
node *zero;
int main()
{
    //#ifndef atom freopen(".in", "r", stdin); freopen(".out", "w", stdout); #endif
    cin >> n;
    zero = new node(0, NULL, NULL);
    zero->left = zero->right = zero;
    root[0] = zero;
    for(int i = 1; i<= n; i++)
    {
        int x; cin >> x;
        if(x> 0)
        {
            root[i] = root[i-1]->insert(0, i);
            num[i] = x;
        }
        else
        {
            x = -x;
            int det = root[i-1]->ask(0, x-1);
            det--;
            //printf("from (%d)\n", det);
            root[i] = root[det]->insert(x, i);
            //printf("max is %d\n", root[i]->ask(0, 1));
        }
        cout << num[root[i]->ask(0, 0)] << endl;
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 16 ms 2572 KB Output is correct
3 Correct 2 ms 2572 KB Output is correct
4 Correct 2 ms 2572 KB Output is correct
5 Correct 16 ms 2572 KB Output is correct
6 Correct 2 ms 2572 KB Output is correct
7 Correct 15 ms 2828 KB Output is correct
8 Correct 2 ms 2828 KB Output is correct
9 Correct 15 ms 2884 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 920 ms 194036 KB Output is correct
2 Correct 910 ms 194036 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 494 ms 194036 KB Output is correct
2 Correct 558 ms 194036 KB Output is correct
3 Correct 801 ms 194036 KB Output is correct
4 Correct 945 ms 198396 KB Output is correct
5 Correct 1082 ms 198396 KB Output is correct
6 Correct 866 ms 199788 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 16 ms 2572 KB Output is correct
3 Correct 2 ms 2572 KB Output is correct
4 Correct 2 ms 2572 KB Output is correct
5 Correct 16 ms 2572 KB Output is correct
6 Correct 2 ms 2572 KB Output is correct
7 Correct 15 ms 2828 KB Output is correct
8 Correct 2 ms 2828 KB Output is correct
9 Correct 15 ms 2884 KB Output is correct
10 Correct 920 ms 194036 KB Output is correct
11 Correct 910 ms 194036 KB Output is correct
12 Correct 494 ms 194036 KB Output is correct
13 Correct 558 ms 194036 KB Output is correct
14 Correct 801 ms 194036 KB Output is correct
15 Correct 945 ms 198396 KB Output is correct
16 Correct 1082 ms 198396 KB Output is correct
17 Correct 866 ms 199788 KB Output is correct
18 Correct 975 ms 199788 KB Output is correct
19 Correct 981 ms 201008 KB Output is correct
20 Correct 994 ms 201008 KB Output is correct
21 Correct 912 ms 208588 KB Output is correct
22 Correct 1116 ms 208588 KB Output is correct