Best plan is participate in AGC29 and after 15 min participate in this round.

ikr

why gritukan decreasing his rating ?

yes

If graph contain odd cycle, answer is zero as no valid assignment can exist.

Otherwise, let us find 2-coloring of each connected component in graph. Say, x nodes are colored red while y nodes are colored black. There are exactly pow(2,x)+pow(2,y) ways to color this component. Take product of this for all components.

Reason of pow(2,x)+pow(2,y). You need sum of edges to be odd. So, one of the value on edge is 2 and other value is either 1 or 3. pow(2,x) assume we assign all red colored nodes with either 1 or 3, giving pow(2,x) choices. Same for y.

It can be easily solved with BFS. And I came up with it a long time later, but I couldn't solve it because of Memory Limit Exceed.

i asked him . he said no !

Graph doesn't have to be connected.

let's say p2[x] is position of x in second permutation, then you need to find number of l2 <= p2[i] <= r2 and l <= i <= r. It's easy to solve it with bit and sqrt decomposition.

In problem E you have to divide both permutations to blocks of length sqrt(n) and than make some calculations.

My idea in E was creating sqrt(n) segment trees, so each of them contains a number of elements in the segment in the array b, that exist in according sqrt-bucket of the array a (t[s][l..r] — number of elements that exist both in in segment a[s*sqrt(n)...(s+1)*sqrt(n)] and b[l...r]). So it should have been some sort of sqrt-decomposition on segment trees.

In the problem MDIST for 2-dim , we have to use 4 segment trees. But since in G there are more than 2 dimensions we have to use 2^k segment trees where k is dimension of the point. Is there any other way to do this problem?

Yours approach looks correct.

It's how you approached it.

I did like this: split array a into halves, start filling from the middle of a (i.e. from right to left of array b).
Denote the element b[n / 2] as x, the two middle elements of a will be x div 2 and x - x div 2 respectively.
For the next elements, let's denote the ones we need to fill in the left half and the right half as L and R respectively. Also, we have MinL as the minimum of filled numbers in the left half, MaxR as the maximum of filled numbers in the right.
Obviously L ≤ MinL and MaxR ≤ R. From there, you can easily split the element from b into two most optimal halves that satisfies both inequalities above.

I did the same mistake :( So, now I have made a macro with int as long long.

Damn it!! I know understood how people solved this question in around 5 minutes. Nice one!

Technically i think this is incomplete, it never says that the graph is connected. So use this solution for every connected component, and then multiply the solution of each one.

Why this is giving TLE for a trivial case although I've implemented exactly this approach. code
UPD: removedmemset() and it ACed :)

I see AC codes having a BIT of ordered_set which also runs in O(N.log^2N).

I coded a solution with segment trees in contest , it didnt worked for me. But It worked when i changed to BIT. Probably constant factor in segment tree increases its runtime

See https://codeforces.com/blog/entry/63807?#comment-476888 See if the 2 ^ (k — 1) approach works for you.

q.erase() runs in O(n) time. Use queue<int> instead of vector

Same here. After writing all that and getting TLE:

solve problem in offline: ordered_set -> BIT

You can pass all tests with naive solution if you want in 5 seconds

It's kind of unfair that the problem setters kept TL so tight that this is happening.

Do you mean a merge sort tree?

Never mind, just got accepted. Never thought memset would pose a problem though.

Actually your C is not hackable since the corresponding rand() sequence does not correspond to a valid input sequence (since you should be able to form some sequence a₁, ..., a_n out of it per the problem statement).

I'm quite confident your C is impossible to hack because it must be possible to recover the array from the input, but having your array as input doesn't correspond to any array from the task.

300000
1 0
1 0
1 0
...

If someone is clearing the whole array of size 300000 for every test, then it'll TLE out.

My O(n*sqrt(n)) solution for E got TLE,and O(n*logn^2) one accepted but slower than yours. How amazing!Maybe you are too strong!

I made a input file to hack your solution but Codeforces don't support such a big file. Here's the link on Dropbox: https://www.dropbox.com/s/rg3bp6crc05h94p/in.txt?dl=0 There isn't any swaps and all the queries ask you about two whole sequences.

There is hacking phase after Educational rounds which lasts for 12 hours then the system testing will begin, it takes around an hour. after all of this your rating will be changed.

You were doing a wrong greedy.

Since the constraints are pretty small, you can just brute force the answer: an answer i will be considered correct if 2i ≤ x ≤ 7i.

When input is n = 29, your code doesn't give any output!

After this step:

std::cin>>x;
rolls=x/7;
x=x%7;

'x' becomes equal to '1' and it can never become '0' in below mentioned conditions from your code:

rolls=rolls+ x/6;
x=x%6;
rolls=rolls+ x/5;
x=x%5;
rolls=rolls+ x/4;
x=x%4;
rolls=rolls+ x/3;
x=x%3;
rolls=rolls+ x/2;
x=x%2;

So it doesn't print the output at this step:

if(x==0){
     printf("%d\n",rolls);
}

PS: Think easy :)

y in power function should be from type long long not long.

a[i]=max(a[i-1],b[i]-a[n-i]) would ensure that a[i]>=a[i-1] which means that sequence is increasing and also a[i]>=b[i]-a[n-i] which means a[n-i]>=a[n-i-1].

Graph doesn't have to be connected. Here is example: n = 3 * 10^5, m = 0 Then this part:

for (int v = 1; v <= n; v++) {
			if (visited[v] == false) {
				color_vertex(v, 0);
				long long red = 0, black = 0;
				for (int i = 1; i <= n; i++) {
					if (visited[i]) {
						if (colored[i] == 0) red++;
						else if (colored[i] == 1) black++;
					}
				}
				ans += (1 << red) % MOD + (1 << black) % MOD;
				ans %= MOD;
			}
		}

will take n^2 time. Another bug in your code is in this line:

ans += (1 << red) % MOD + (1 << black) % MOD;

black and red can be bigger than 64. Better option is to just count every 2^k % MOD at the start of your program:

POT[0] = 1;
for (int i = 1; i < N; i++)
    POT[i] = (POT[i - 1] * 2) % mod;

My way to solve this problem (not very efficient, but it passed):

Represent each number as a point , then the problem will become count the number of points in the rectangle with two opposite vertices (l_a, l_b) and (r_a, r_b). You can easily solve this problem with compressed 2D BIT.

This loop is used in BIT, I guess.

i & -i gets the least significant bit out. This is good read.

a *= a % c means a = a * (a%c), which is not a = (a*a)%c, so it will overflow.

But why?

I think the issue is in using cin/cout with scanf/printf.

Declaring vector for graphs and color inside main function instead of globally doesn't seems to be a wise decision.

Here you go Submission