### EmilConst's blog

By EmilConst, 3 years 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

• +29

| Write comment?
 » 3 years ago, # |   +13 That's great, thanks.
 » 3 years ago, # | ← Rev. 3 →   +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.
 » 3 years ago, # | ← Rev. 3 →   +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)$.
 » 3 years ago, # |   -8 Is there any source to upsolve IZhO 2020?
•  » » 2 years ago, # ^ |   +5 You can do it in group ACM in Kazakhstan here is the link: https://codeforces.com/group/Uo1lq8ZyWf/contests
 » 2 years ago, # | ← Rev. 2 →   -10 .
 » 10 days ago, # | ← Rev. 4 →   0 Benq why did you do the analysis for the tasks of the first day and did not do it for the remaining tasks of the second day. If you can do task day2 C do this please.