L: We construct tree greedy , then solve problem with centroid-decomposition code: https://ideone.com/kzZmuP

L: Once we have the shortest paths tree, computing the answer can be done using centroid decomposition.

The tree can be computed with Dijkstra's algorithm, modified to prefer parents with a smaller path from the root (with respect to the lexicographical order). Checking if a path is smaller can be done with binary lifting, in a way similar to the computation of LCAs.

H. Let p = x - y, q = y - z, r = z - 1. Then, in pqr-space, a subhill is of the form p ≥ const, q ≥ const, r ≥ const, p + q + r ≤ const.

Fix the value of p + q + r (try all O(N) possibilities). Now the task is a standard 3D-sum problem. In total it works in O(N⁴).

I believe it's also possible to solve it in O(N³) but looks quite messy.

H: Let's split each 3d update/query into <=100 2d updates/queries. For fixed y, we get update/query on some rectangle. First do all updates using inclusion/exclusion (adding +-1 to points (X,Z) to denote adding +-1 to all x>=X, Z>=z and then taking partial sums to find value at position (x,z)); now you can answer each 2d sum query in O(1) using partial sums once again.

K: Kind of divide-and-conquer. Let's assume that each query contains element n/2. In this case we can calculate dp for each suffix of the left part of the array and for each prefix of the right part; now in order to answer a query you can combine corresponding suffix of first part and prefix of second part in O(D). Now we are left with queries which are completely contained within left or right subarray; OK — let's solve them recursively. That gives us O(D * M) to answer all queries and O(N * D * logN) to calculate all DP values at each level of recursion.

Is there any new upsolving? When I access upsolving system, the last problem is old -> "O-17 Sphenic Numbers".

Where can i find problems?

F?

B?

D?

Does anybody know when (approximately) contest will be unfrozen? Just curious.

Вброшу немного:

1) Ребята, очень у вас агрессивный кеш в таблице результатов до сих пор. Она отставала на 1/4 на несколько десятков минут, на опенкапах на 10-20 минут стабильно. Приходится смотреть ее на главной opencup'а, там она гораздо свежее. Сегодня плюс она во времени у нас прыгала на несколько часов иногда.

2) Я на 1/8 еще баг сдал, до сих пор не поправили: вы компилируете и запускаете на разных машинах. С этими pragma'ми почти любой исходник получает RE:

#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("avx,tune=native")

Это очень грустно, потому что не получится написать такой код: "если платформа поддерживает SSE/AVX, используй нужную инструкцию".

Пример посылки: #5461274

3) Нельзя ли компилятор обновить еще? Либо, хотя бы, c++14 разрешить на опенкапах посылать. На 1/8 и 1/4 такая возможность была, сейчас ее нет.

Problem A is copied from this one.

And I think problem F is also copied from problems of Multi-University Training Contest in China. In my mind, I have solved this problem before.

how to solve C??