Untitled

#define F __attribute((optimize("Ofast")))
#define MAXS 4*1000000+3
#define MAX_HASH 20007
#define ull unsigned long long
   
struct CELL
{
    int parent, skipParent, level;
    ull n1, n2;
    int hashNext;
};
   
CELL cells[12007];
int cid;
   
// --------  hashmap ----------
   
int hashmap[MAX_HASH];
   
F void strToull(char *s, ull& n1, ull& n2)
{
    n1 = n2 = 0;
    int cc = 0;
    while (*s != '\0')
    {
        int d = 0;
        if (*s >= 'a' && *s <= 'z') d = (*s - 'a' + 1);
        else d = (*s - 'A' + 1 + 27);
   
        if (cc > 6) n2 =( (n2 << 6) | d);
        else n1 = ((n1 << 6) | d);
   
        s++;
        cc++;
    }
}
   
F void addToHash(int id)
{
    int h = cells[id].n1 % MAX_HASH;
    cells[id].hashNext= hashmap[h];
    hashmap[h] = id;
}
   
F int getFromHash(char *str)
{
    ull _n1, _n2;
    strToull(str, _n1, _n2);
    int h = _n1 % MAX_HASH;
    int id = hashmap[h];
    while (id && !(cells[id].n1 == _n1 && cells[id].n2 == _n2))
        id = cells[id].hashNext;
    return id;
}
   
// -------- Segment Tree --------
   
int ST[MAXS];
   
F void process(int start, int end, int left, int right, int ind, bool getCount, int & count)
{
    if (right < start || left > end)
        return;
   
    if (start >= left && end <= right)
    {
        if (getCount) count = ST[ind];
        else ST[ind] += 1;
        return;
    }
   
    ST[2 * ind + 1] += ST[ind];
    ST[2 * ind + 2] += ST[ind];
    ST[ind] = 0;
   
    int mid = (start + end) / 2;
    process(start, mid, left, right, 2 * ind + 1, getCount,count);
    process(mid + 1, end, left, right, 2 * ind + 2, getCount, count);
}
   
   
F int processUtil(int l, int r, bool getCount = false)
{
    int ret = 0;
    process(0, 1000000, l, r, 0, getCount, ret);
    return ret;
}
   
// --------
F void init(char mAncestor[], int mDeathday)
{
    cid = 1;
    for (int i = 0; i < MAX_HASH; i++) hashmap[i] = 0;
    for (int i = 0; i < MAXS; i++) ST[i] = 0;
   
    cells[cid].level = 0;
    cells[cid].parent = -1;
    cells[cid].skipParent = 1;
    strToull(mAncestor, cells[cid].n1, cells[cid].n2);
    addToHash(cid);
    cid++;
    processUtil( 0, mDeathday);
}
   
F int add(char mName[], char mParent[], int mBirthday, int mDeathday)
{
    int _pid = getFromHash(mParent);
   
    int curr_level = cells[_pid].level + 1;
    cells[cid].level = curr_level;
    cells[cid].parent = _pid;
    cells[cid].skipParent = cells[_pid].skipParent;
    if (cells[cid].level % 50 == 0)
    {
        cells[cid].skipParent = _pid;
    }
    strToull(mName, cells[cid].n1, cells[cid].n2);
    addToHash(cid);
    cid++;
    processUtil(mBirthday, mDeathday);
    return  curr_level;
}
   
F void bringToLevel(int& start, int dest)
{
    while (cells[start].level > dest)
    {
        if (cells[start].level - dest > 50)
        {
            start = cells[start].skipParent;
            continue;
        }
        start = cells[start].parent;
    }
}
   
F int distance(char mName1[], char mName2[])
{
       
    int _id1 = getFromHash(mName1);
    int _id2 =getFromHash(mName2);
   
    int _level1 = cells[_id1].level;
    int _level2 = cells[_id2].level;
   
    int minLevel = _level1 > _level2 ? _level2 : _level1;
   
    bringToLevel(_id1, minLevel);
    bringToLevel(_id2, minLevel);
   
    while (cells[_id1].skipParent != cells[_id2].skipParent)
    {
        _id1 = cells[_id1].skipParent;
        _id2 = cells[_id2].skipParent;
    }
    while (_id1 != _id2)
    {
        _id1 = cells[_id1].parent;
        _id2 = cells[_id2].parent;
    }
   
    int dist1 = _level1 - cells[_id1].level;
    int dist2 = _level2 - cells[_id2].level;
   
    return dist1 + dist2;
}
   
F int count(int mDay)
{
    return processUtil(mDay, mDay, true);
}