// x86_64-w64-mingw32-g++ -std=c++11 -m64 -Ofast -s -o timer.exe timer.cpp
#include <stdint.h>
#include <string.h>
#include <stdio.h>
#include <chrono>
#include <functional>

class Node {
	friend class Timer;
	Node* next{nullptr};
	int64_t runTime;
public:
	virtual ~Node() {}

	bool inTimer() const {
		return next != nullptr;
	}

	int64_t getRunTime() const {
		return runTime;
	}

	virtual int64_t onTimer() {
		return 0;
	}
};

constexpr int SLOT_SHIFT = 8;
constexpr int SLOTS_COUNT = 5;
constexpr int SLOT_MASK = (1 << SLOT_SHIFT) - 1;
constexpr int SLOT_SIZE = (1 << SLOT_SHIFT) * SLOTS_COUNT;

class Timer {
	Node* nodeHeads[SLOT_SIZE + 1];
	int64_t curTime;
public:
	Timer(int64_t curTime_) : curTime(curTime_) {
		memset(nodeHeads, 0, sizeof(nodeHeads));
	}

	int64_t getCurTime() const {
		return curTime;
	}

	void add(int64_t runTime, Node* node) {
		if (node->next)
			throw "added already";
		int idx;
		const int64_t dt = runTime - curTime;
		if (dt < 1LL << SLOT_SHIFT) {
			if (dt < 0)
				idx = runTime < curTime ? (int)(runTime = curTime) & SLOT_MASK : SLOT_SIZE;
			else
				idx = (int)runTime & SLOT_MASK;
		}
		else if (dt < 1LL << (SLOT_SHIFT * 2))
			idx = (1 << SLOT_SHIFT) + ((int)(runTime >> SLOT_SHIFT) & SLOT_MASK);
		else if (dt < 1LL << (SLOT_SHIFT * 3))
			idx = (2 << SLOT_SHIFT) + ((int)(runTime >> (SLOT_SHIFT * 2)) & SLOT_MASK);
		else if (dt < 1LL << (SLOT_SHIFT * 4))
			idx = (3 << SLOT_SHIFT) + ((int)(runTime >> (SLOT_SHIFT * 3)) & SLOT_MASK);
		else if (dt < 1LL << (SLOT_SHIFT * 5))
			idx = (4 << SLOT_SHIFT) + ((int)(runTime >> (SLOT_SHIFT * 4)) & SLOT_MASK);
		else // SLOTS_COUNT overflow
			idx = SLOT_SIZE;
		Node* const head = nodeHeads[idx];
		if (!head)
			node->next = node;
		else {
			node->next = head->next;
			head->next = node;
		}
		nodeHeads[idx] = node;
		node->runTime = runTime;
	}

	void update(int64_t curTime) {
		int64_t t = this->curTime;
		if (curTime < t)
			return;
		for (int idx = (int)t & SLOT_MASK; ; ) {
			Node* head = nodeHeads[idx];
			if (head) {
				this->curTime = t;
				do {
					nodeHeads[idx] = nullptr;
					for (Node* node = head->next; ; ) {
						Node* const next = node->next;
						node->next = nullptr;
						const int64_t nextTime = node->onTimer();
						if (nextTime > 0)
							add(t + nextTime, node);
						if (node == head)
							break;
						node = next;
					}
				} while ((head = nodeHeads[idx]));
			}
			if (t == curTime) {
				this->curTime = t;
				return;
			}
			if ((idx = (int)++t & SLOT_MASK) == 0) {
				int i = 1;
				while (((t >> (i * SLOT_SHIFT)) & SLOT_MASK) == 0 && i < SLOTS_COUNT - 1)
					i++;
				for (; i > 0; i--) {
					int base = i << SLOT_SHIFT;
					int shift = i * SLOT_SHIFT;
					int idx1 = base + ((int)(t >> shift) & SLOT_MASK);
					if ((head = nodeHeads[idx1])) {
						nodeHeads[idx1] = nullptr;
						base -= 1 << SLOT_SHIFT;
						shift -= SLOT_SHIFT;
						for (Node* node = head->next; ; ) {
							Node* const next = node->next;
							idx1 = base + ((int)(node->runTime >> shift) & SLOT_MASK);
							Node* const head1 = nodeHeads[idx1];
							if (!head1)
								node->next = node;
							else {
								node->next = head1->next;
								head1->next = node;
							}
							nodeHeads[idx1] = node;
							if (node == head)
								break;
							node = next;
						}
					}
				}
			}
		}
	}
};

class Rand {
	int64_t seed;
public:
	Rand(int64_t seed_) : seed(seed_) {}

	int64_t rand() {
		const int64_t r = seed * 6364136223846793005LL + 1442695040888963407LL;
		seed = r;
		return r;
	}
};

struct State {
	Rand rand{0};
	Timer timer{(int)rand.rand()};
	int64_t runCount{0};
};

class TestNode : public Node {
	State& state;
public:
	TestNode(State& state_) : state(state_) {}

	int64_t onTimer() override {
		State& s = state;
		const int64_t runTime = getRunTime();
		const int64_t curTime = s.timer.getCurTime();
		if (runTime != curTime) {
			printf("ERROR: 0x%llX != 0x%llX\n", runTime, curTime);
			throw "assert failed";
		}
		s.runCount++;
		return s.rand.rand() & 0x1ffff;
	}
};

int main() {
	const auto t0 = std::chrono::high_resolution_clock::now();
	State state;
	Timer& timer = state.timer;
	const int64_t curTime = timer.getCurTime();
	for (int i = 0; i < 100000; i++)
		timer.add(curTime + (state.rand.rand() & 0x1ffff), new TestNode(state));
	for (int i = 0; i < 86400000; i += 33)
		timer.update(curTime + i);
	const auto t1 = std::chrono::high_resolution_clock::now();
	const auto t = std::chrono::duration_cast<std::chrono::microseconds>(t1-t0).count() / 1000;
	printf("%lld, %d ms\n", state.runCount, static_cast<int>(t));
	return 0;
}