Code

I think it is $$$O(q / K * (n + m + q + K^2 + K * (log(n) + K / 64)))$$$.

Unfortunately for $$$1 ≤ n ≤ 50000; 1 ≤ m ≤ 150000; 1 ≤ q ≤ 250000, K = 456$$$ it works more than 10 seconds.

$$$K / 64$$$ is for queries when I calculate (on & have[id[u[i]]]).count() and $$$K ^ 2$$$ is clearing $$$have$$$.

I am solving 398D - Instant Messanger and don't understand why my solution is so slow, I tried to change values of $$$K$$$ and the best results I got is 4211 ms with $$$K = 2000$$$.

UPD : I made $$$K = 6000$$$ and got Accepted.

I can't solve this problem : https://lightoj.com/problem/lcs-revisited.

I can calculate the length of LCS of two strings, but don't have idea for this problem.

I would be glad for your help.