oj.uz

답안 #43047

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
43047 2018-03-08T09:28:10 Z PowerOfNinjaGo Editor (BOI15_edi) C++14
20 / 100
 413 ms 128960 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 = 1e5+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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 248 KB Output is correct
2 Correct 15 ms 2656 KB Output is correct
3 Correct 1 ms 2656 KB Output is correct
4 Correct 2 ms 2656 KB Output is correct
5 Correct 15 ms 2724 KB Output is correct
6 Correct 1 ms 2724 KB Output is correct
7 Correct 14 ms 2888 KB Output is correct
8 Correct 1 ms 2888 KB Output is correct
9 Correct 15 ms 2888 KB Output is correct

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 413 ms 128960 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 378 ms 128960 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 248 KB Output is correct
2 Correct 15 ms 2656 KB Output is correct
3 Correct 1 ms 2656 KB Output is correct
4 Correct 2 ms 2656 KB Output is correct
5 Correct 15 ms 2724 KB Output is correct
6 Correct 1 ms 2724 KB Output is correct
7 Correct 14 ms 2888 KB Output is correct
8 Correct 1 ms 2888 KB Output is correct
9 Correct 15 ms 2888 KB Output is correct
10 Runtime error 413 ms 128960 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Halted 0 ms 0 KB -