Sorry, we fixed it now.

Anyway, it was a link to the ER22 editorial, so it would not help anyone with this round.

The contest will surely delay, it is tradition.

Judgement failed, too >:'(

Mine also >-<

same here

the answer is always l[i] or r[i] + 1 for some i , so just coordinate compress these points and then use normal segtree.

I think we can compress the value of L and R and then build a segment tree with the new value (1 — 200000) and then use lazy-constructed segment tree as you said.

Sparse Segment Tree gives MLE on test 15 :( But shouldn't that pass the ML? It creates ~ 64 nodes per update. Each node has one long long and one short.

C was a binary search :)

the sum of the digits can't be large, so there's not many numbers x such that the check x - digitsum(x) >  = s is interesting. Check them all and add the rest in O(1), I checked only the interval [s..min(s+200,n)].

It can be proved that if a > b then a — sum_of_digits(a) >= b — sum_of_digits(b) so we can do binary search to find the smallest n that n — sum_of_digits(n) >= s

All numbers from s+9*18+1 to n are really big. So you can check numbers from s to s+9*18 and add max(0, n — s+9*18)

C is really a brute force problem.

It was supposed to be A.

Just iterate through s+1 to max(n, s+160) and find where
this condition met -> (s+i) — sum_of_digit(s+i) >= s.
then just print (n — (s + i) + 1).
if not met then just print 0.

this.

I got AC with NlogN.

Click

Maybe, At least NlogN solution can pass pretest

Yeah I got AC for now with something that looks like nlog^2n

brute force is enough for C. Dont worry!!

here you go.

For each element, let the number of subarrays in which it is the min be cnt_min[i] and the number of subarrays in which it is the max be cnt_max[i]. Answer is sum of arr[i]*(cnt_max[i]-cnt_min[i]).

To find cnt_max[i], for each index i, find the closest indices to its left and right such that value there is > arr[i]. This can be done in cumulative O(n) time using stack. Similar for cnt_min[i].
Take care of duplicate values.

Code

The basic idea is for each i find Nmx[i] — the number of subarrays that will have a[i] number as maximum. Then do final_answer += Nmx[i] * a[i]. Similarly find Nmn[i] — number of subarrays in which a[i] will be the minimum number, and do final_answer -= Nmn[i] * a[i].

Nmx can be found in O(N) time. To find Nmx[i], you have to find Rmx[i] and Lmx[i] such that a[i] is maximum among all numbers in the segment [Lmx[i], Rmx[i]]. Rmx and Lmx arrays can be obtained with a forward sweep and a reverse sweep of the original array.

Similarly find Nmn array.

Read this tutorial to learn how to solve similar problems involving XOR using trie.

In this problem, maintain a trie in which numbers are inserted/removed in the decreasing order of bits in their binary representation. Now, for the query part, just traverse along the path specified by P and consider all cases in which you can get XOR < L.
eg. if next bit of P is 0 and next bit of L is 1, you can add all the numbers along the 0-edge to the answer and then move along the 1-edge (because for all numbers inserted in subtree of 0-edge, their XOR with P will be < L).

You can see all the cases in my code. Code

Hacked.

They are :c We really try to balance out problemsets but everytime it ends up with lots of ds problems.

I guess that it is actually fine in context of ERs because education in competitive programming is mostly about learning algos and data structures. Still somehow I am not pleased with the quality of contests...

overflow.(btw, you declared n as long long and answer as int lol)

Your logic works, but the result of k1 choose 3 doesn't fit in an int type, you should use long long int.

As usual :D