Maintain prefix XOR. Partition the indices with two of them in the same set if their prefix XORs are same. Maintain separate count for odd and even indices in each of the partitions. Answer will be the sum over all partitions of (odd choose 2) + (even choose 2).

Yeah, I received something similar one. But a different username. Looks like a bot.

Brute force the value of t_n. Given a_i, b_i, and t_i + 1, it is easy to show that there can be at most one t_i that satisfies the given constraints.

The complexity of sqrt is actually implementation dependent. Usually, it is implemented using Newton's or similar methods which are .

I think you probably meant

Shouldn't in Task E, Lemma 3 should say f(i) is non-increasing?

Can you please explain what does f[n][j] stand for in your code?

In Problem E, how is the time complexity O(q * logq)? After finding the first interval that intersects with the query, one needs to go over all the following intervals that intersect the query. That should amount to for query i, and hence, O(q²) overall. However, this passes system tests 34180929. What am I missing?

Why is it so? Just curious.

But in both cases we must add 3 arithmetic progression to the segment of array d. Its well known task, which can be done by adding/subtracting values in start and end of segment offline.

Can you please elaborate a bit(or point to some reference) on this well known task?

Thanks, got AC with applying 1 and 2. 23512670. Also, it was the first time, I heard of non-recursive segtree. Thanks for that too!

I guess number of nodes in segment tree is at most 2^(ceil(log2(n))+1) = 2^19. Please correct me here.

I implemented the idea as per your explanation, but getting TLE. 23502332. Any suggestions?

Exactly, what does the entry dp[i][j] represent? It seems as if it represents "number of ways to color subtree rooted at i, such that the closest black node to i is j units away". Is my understanding correct?

Problem D: My solution is O(4*n*m) and it is judged as TLE on test case 24. Can someone please have a look and suggest what's wrong? My Code

Duh,Me a noob! Thanks

12061940, working perfectly on my system but WA at #1. Please help

550C- Which data type should I choose for the integer n <= 10^100 in C++? I am using long long, but with it test# 23 gives incorrect answer probably because of limit of long long.

485-B Test# 7 gives correct answer on my compiler but wrong on the online one. Used long int (C++11) but still not working. Any suggestions?