Mod 0 is equal to a division by 0 and it is undefined behavior. Runtime error on Codeforces is caused by diagnostics that Domjudge does not have (actually, i am not sure that diagnostics are throwing RE, but the main rule that with UB, you won't know if it will give you WA or RE or something else).

You are right, after the reduction you can solve the last part with $$$O(n \log n)$$$ preprocessing and $$$O(\log n)$$$ per query with persistent segment trees.

Lets solve our queries offline and sort them by $$$r$$$ coordinate. Lets create array $$$a$$$ of length $$$n$$$ such as $$$a[k]$$$ = $$$ans(s_{k..r})$$$ — $$$ans(s_{k+1..r})$$$. Then the answer to our query $$$[l..r]$$$ would be $$$\displaystyle \sum_{i = l}^r a[i]$$$. Easy to see that $$$0 \leq a[x] \leq 1$$$.

We need to find a way to transition from $$$r-1$$$ to $$$r$$$. $$$a[k]$$$ right now is equal to $$$ans(s_{k..r-1}) - ans(s_{k+1..r-1})$$$. So we just need to consider the longest palindrome with symbol at position $$$r$$$ (lets say this palindrome is $$$\displaystyle s_{x..r}$$$ with length equal to $$$len$$$). Lets say that this palindrome is unique, then we are adding $$$1$$$ to $$$a[x]$$$ (because all strings that start at position $$$j \leq x$$$ will contain it, and all strings that start at position $$$j \gt x$$$ will not have it.) What if there is some occurrence of our $$$\displaystyle s_{x..r}$$$? Lets consider the maximum pos $$$y \neq x$$$ such as $$$\displaystyle s_{y..y + len - 1} = s_{x..r}$$$. We need to subtract $$$1$$$ from $$$y$$$ and still add $$$1$$$ to $$$x$$$. (because only the last occurrence of unique palindrome changes our array $$$a$$$). And we can maintain the position of last occurrence of palindrome with eertree.

How to make this algorithm work online? Use persistent segtree for every $$$r$$$.

334280775 or code on ideone

You can solve it with persistent double-ended eertree (6.1.2) in $$$O(n \sqrt q (log(n) + log(\sigma))$$$ but its really painful to implement and I hope there is another way to solve this problem.

Basically, the number of nodes in eertree (minus $$$1$$$) is equal to the number of distinct palindromic substrings, but in our queries, we have some set of strings. We need to find a way to concatenate strings that are in the set into some single string without creating new palindromic substrings. The simplest way is to take some string $$$t$$$ with length $$$2$$$ that contains $$$2$$$ different symbols that are NOT in $$$\sigma$$$ (for example: "!#", "*&", etc.) and create string $$$u = s_{1} + t + s_{2} + t + \dots + s_{n-1} + t + s_{k} + t$$$ ($$$k$$$ is equal to the size of the set of some query and $$$s_{i}$$$ is the i-th string in this set) (for example: if the set is {"abc", "aa", "a"}, $$$t$$$ = "!#", then $$$u$$$ = abc!#aa!#a). And we can see that we counted every palindromic substring of every string in the set (because they are in our string $$$u$$$) and we also counted $$$2$$$ extra palindromic substrings that are the first and second characters of the string $$$t$$$ (because they are of length $$$1$$$). We can prove that there won't be more extra substrings because of $$$t$$$.

And if we make string $$$p = s_{1} + t + s_{2} + t + \dots + s_{n-1} + t + s_{n} + t$$$ we have transformed our problem into counting the number of distinct palindromic substrings in some range $$$p_{l..r}$$$ (and we need to subtract $$$2$$$ from our answer because of string $$$t$$$).

Centroid decomposition for E 298885664 Can this be hacked?

B can be cheesed, bad testcases i guess Link

use long long ($$$1 \leq a_i \leq 10^9$$$) 224508834

Output

For each test case, output two lines: in the first line, output the number of strong vertices, and in the second line, output all strong vertices in ascending order.

1pic 2pic

I was trying explaining it by myself, but editorial is better. In the first pic the red is what have changed, blue is what remaining the same. So we can just swap the modulo 2 of two adj. indexes we want, and with swap $$$(s_{i}, s_{i+2})$$$ we can place any chars we want. For you i made the same with $$$n = 6$$$ and $$$k = 4$$$.

Swap $$$(s_{i}, s_{i+2})$$$ means we can sort all the chars in odd and even positions. If $$$k$$$ is even we can change the parity of any char we want (i.e. from odd to even and from even to odd) thus we can sort all string.

From codeforces telegram:

Unfortunately, there was a power outage in the city today, which caused a disruption in Codeforces' operation. At this moment, Polygon and other services are already operational, and Codeforces is close to being up and running. We estimate that the start will happen in about 15-20 minutes. Considering that the "Codeforces Round 893 (Div. 2)" was expected to start around this time, we have decided to postpone the start of the round by 1 hour. Therefore, the round will begin at 14:35 (UTC) / 17:35 (MSK).

tldr: site were down for like an hour and started working ~10 mins before contest were about to start so codeforces decided to postpone

Others cant hack (unreadable)