#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);
}