### EmilConst's blog

By EmilConst, 10 months ago,

A month ago IZhO 2020 was held in Almaty, Kazakhstan. Thanks to Tima we can submit our solutions here. Here is editorial for problems day1 A, day1 B, day2 C. Please write solutions for other problems in comments.
Benq has published his codes for all problems here.

Observation
Final
Observation 1
Observation 2
Observation 3
Observation 4
Final

 » 9 months ago, # | ← Rev. 2 →   +29 Day 2 B (by request)Note: It's similar to C from here.Special case: $l=r$ Getting the # of vertices that are at most a distance $k$ away from a fixed vertex is a well-known problem. It can be done with centroid decomposition and a table that stores prefix sums at each level of the decomposition. General case:For each query, consider the centroid $c$ of the tree and the computer $i$ that determines its infection time (namely, the $l\le i\le r$ which maximizes $t_i+dist(c,v_i)$). This can be computed with a segment tree.Then the latest infection times for all computers $d$ outside the subtree of $c$ corresponding to $v_i$ will satisfy $infect_d=infect_c+dist(c,d)$. The number of such vertices that are infected within time $t$ can be computed as in the special case. Then we can recursively deal with the vertices inside the subtree corresponding to $v_i$ by considering the centroid of this subtree, and so on. Note that viruses that originate outside the subtree corresponding to $v_i$ must still be considered; this is what $extra$ is for in my solution.This can be done in $O(N\log N+Q\log^2N)$ if we process all updates before all queries.
 » 9 months ago, # | ← Rev. 2 →   +36 Day 1 C (by request)Suppose that we fix $j$ and we want to find the number of pairs $(i,k)$ which work. For a fixed element $x$, let $pre[x]$ equal the maximum $J\le j$ such that $a_J=x$. Similarly, let $nex[x]$ equal the minimum $J>j$ such that $a_J=x$. Then $(i,k)$ is okay if for all $x$, either $i\le pre[x]$ and $nex[x]\le k$ or $pre[x]\max(a[i+1\ldots n])$ after every modification. Use a lazy segment tree that computes the minimum as well as the number of minimums, and supports addition updates on a range. The operations required for this problem are slightly more complex than those needed for that task (see the code for details).Start with all the pairs $(pre[x],nex[x])$ for $j=1$. For each $j$ in increasing order, add the number of pairs $(i,k)$ which work for that $j$ to the answer. Then when you increase $j$ by one, only one of the pairs $(pre[x],nex[x])$ changes (which corresponds to a constant number of updates to the segment tree). The functions "ad" and "del" correspond to adding and deleting a pair $(pre[x],nex[x])$, respectively. The meanings of nex and pre in the code might not be exactly the same as what I mentioned above. The overall time complexity is $O(N\log N)$.