Some of the problems were not new.

Please don't downvote :(

Do both :)

Yes.

Indeed. I didn't know it was possible to calculate this sum effectively... Until I solved this problem today.

f(n) = 1^k + 2^k + ... + n^k is a polynomial of degree (k + 1). So, using Lagrange's interpolation formula, it's possible to compute f(n) in O(klog(k)).

Oh, yes! Math!

Thanks for nice words. I tried to contribute cool tasks. At least I hope problems D and E were interesting for solving :) Both tasks are easy for implementation and I will try to invent something similar in future !

Как?

лол, а я тут вообще sqrt-декомпозицию запрогал и получал TLE17:D

I knew this idea and yet I couldn't solve :(

не знаю правильное мое решение или нет, но претесты вроде прошли.

Я делал так, запускаем дфс из каждого ребенка корня и нахожу для каждого листа этого поддерева кратчайшее расстояние. После этого сортирую вершины по их дистанции и после этого делаю так что все расстояния были различными. Ответ будет максимальное из этих расстояний из каждого поддерева. Почему нам нужно именно кратчайшее расстояние не до корня, потому что в корень мы можем прийти одновременно из все его сыновей.

Почему это может работать,жадно вначале поднимаем всех тех,кто ближе. И если есть свободное окно поднимаем еще кого-то.

ссылка на код Your text to link here...

one way is to split array in sqrt(n) blocks. for each block, you keep an set and do binary search on it

You can do some pre-processing.
For each position, store the position of the next number that is not equal to it.
Just traverse the array from right to left
if array[i + 1] != ar[i] , then nextUnequal[i] = i + 1
else nextUnequal[i] = nextUnequal[i + 1]
Now when you have a query(L,R,X) check A[L] if it's not equal to X, return L otherwise look at nextUnequal[L] if that's <= R, return that else return -1

For each index of the array keep the index of the next element which is not equal to current.
Then the answer for query can be obtained like this:
1. if (a[l] != x) print l
2. else if (nxt[l] > r) print -1
3. else print nxt[l]

For each position in array remember the last position of a number different that what you have at that position(denote it d[i]), then for each query check if tab[r] != x — r is the answer, if tab[r] == x and d[r] >= l — answer is d[r], else -1

What i did was to find maximum number in the interval.

Then i also found minimum number in interval.

If both are the same and they are equal to the number we dont want it to be equal to , we output -1.

Else we look which of min and max are different from it and output one of them.

But there are better solutions.

I did it a long way by having 2 segment tree, one which reports the minimum and other which reports maximum in the range [L, R]. If both of them are equal and equal to x then print -1 else find the position of one not equal to x. Since the numbers range is [1,10**6], store indexes of each number in a vector and then binary search on them to find position. Complexity: O((n+m)logn)

can be solved using DP in O(N+M) time. The idea is to calculate the maximum length of subarray for each position such that the subarray contains the same number as the one in that position. You can do this in O(N) time

Then for each query go to array[l] . If this is not equal to x, tada! else jump to the position denoted by array[l] and the length of the precalculated subarray for position l. If this is within range, return the position, else -1

Consider all children of 1, let them be v. We can calculate answers for each v separately, taking the maximum answer.

Now, for each v, find all leaves that belong to v, and record their distance. Sort them in decreasing order, and the answer is max(d[i]+i) for 0-based distance array. The reason is that we can think in reverse way: the ants move from root to leaves, and we always want the furthest ant to move first.

Btw, this question has appeared (exact problem) some year ago in a chinese contest.

See http://mirror.codeforces.com/blog/entry/23358?#comment-277833

Simple interpolation: https://en.wikipedia.org/wiki/Lagrange_polynomial.

What ?

check 15945814 tree1 stores index of maximum element in a range and tree2 stores index of minimum.

I solved C with partial sums. Say we have to answer a query (X, Y, C): if sum of numbers in tha range [X, Y] is divisible by (Y-X+1) and sum in range [X, Y] divided by (Y-X+1) equals C then we have no element in range [X, Y] which is different from C. If we have a different element, we can binary search for the position of that different element.

Here is my solution

LE: Nevermind, I missed a case

There are many hacked solutions for A and B task, so possible some tricky testcases exist ;)

There was no time limits problem in your solution. Actually you have used System class to print the output which is quite slow. Also you have used println which is slower especially when it is used directly by System class(writing on console sending bytes, flushing the screen etc). To make it faster create an instance of PrintStream class and use that instance to write to the console. print("\n") uses '\n' as linefeed character and println() terminate the string with new line character depending on the platform. Best to use is '%n' with printf() in java.

15949731 15949638 15949630

May be .bat with tests.cpp.

My approach-

Build a segment tree in nlogn where each node has a vector of elements of its subtree in sorted order. 2 adjacent segments will have sorted elements and so merging can be done in O(n) leading to a total build complexity of nlogn. Queries will find the range in a segment which has 'x' and then return an index outside this range. Complexity of each search is therefore log^2(n).

I realized after contest that all we need is minimum and maximum of a range to find any position which does not have x . Stupid me :/