Submission #43048

#	Time	Username	Problem	Language	Result	Execution time	Memory
43048		PowerOfNinjaGo	Editor (BOI15_edi)	C++14	100 / 100	1116 ms	208588 KiB

edi

//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 / 20
• Subtask 2: 15 / 15
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37