Implicit segment tree problem

cf_spb_seg2_a_dyn.cpp

// solution for http://codeforces.com/gym/100094/attachments/download/1239/20122013-tryenirovka-spbgu-b-6-zaprosy-na-otryezkye-dyeryevo-otryezkov-2-ru.pdf
// problem A using Implicit (dynamic) segment tree
// For unknown reason it fails test 8 with TLE
// Nevertheless might be useful as an example of dynamic implementation
#include <bits/stdc++.h>
using namespace std;
typedef long long int lint;
const lint BIG = 1e9 + 1;

struct Node {
    lint data;
    shared_ptr<Node> left, right;
    Node() : data(0) {}
};

typedef shared_ptr<Node> NodePtr;

NodePtr root(new Node);

int findN1(NodePtr cur, lint L, lint R, lint l, lint r) {
    if (cur == nullptr || R < l || r < L) return 0;
    if (L >= l && R <= r) return cur->data;

    lint M = L + (R - L)/2;
    return findN1(cur->left, L, M, l, r) + findN1(cur->right, M+1, R, l, r);
}

int findN0(NodePtr cur, lint L, lint R, lint l, lint r) {
    if ( R < l || r < L) return 0;
    if (cur == nullptr) {
        //cout << L << " " << R << endl;
        return min(R, r) - max(L, l) + 1;
    }
    if (L >= l && R <= r) return R - L + 1 - cur->data;

    lint M = L + (R - L)/2;
    return findN0(cur->left, L, M, l, r) + findN0(cur->right, M+1, R, l, r);
}

int findIndOf1st0(NodePtr cur, lint L, lint R, lint l) {
    //cout << L << " " << R << endl;
    if (L == R) return L;
    if (cur == nullptr)
        return max(l, L);
    lint M = L + (R - L)/2;
    lint cntleft = findN0(cur->left, L, M, l, BIG);
    if (cntleft >= 1)
        return findIndOf1st0(cur->left, L, M, l);
    return findIndOf1st0(cur->right, M+1, R, l);
}

// update the whole tree - so every node contains sum of corresponding segment, not just part of it
void upd(NodePtr cur, lint L, lint R, lint ind, lint val) {
    if (L == R) {
        cur->data = val;
        return;
    }

    lint M = L + (R - L)/2;
    if (ind <= M) {
        if (cur->left == nullptr)
            cur->left.reset(new Node);
        cur->data -= cur->left->data;
        upd(cur->left, L, M, ind, val);
        cur->data += cur->left->data;
    } else {
        if (cur->right == nullptr)
            cur->right.reset(new Node);
        cur->data -= cur->right->data;
        upd(cur->right, M+1, R, ind, val);
        cur->data += cur->right->data;
    }
}

int main(int, char**) {
    std::ios::sync_with_stdio(false);
    ifstream fin("floor4.in");
    ofstream fout("floor4.out");
    lint n;
    fin >> n;
    for (int i = 0; i < n; ++i) {
        //lint x;
        //cin >> x;
        //upd(root, 0, BIG, x, 1);
        //cout << findN0(root, 0, BIG, 0, BIG) << endl;
        //continue; 
        
        lint cmd;
        fin >> cmd;
        if (cmd > 0) {
            lint ind = findIndOf1st0(root, 0, BIG, cmd);
            fout << ind << endl;
            upd(root, 0, BIG, ind, 1);
        } else {
            upd(root, 0, BIG, -cmd, 0);
        }
    }

    return 0;
}