No, but if you tell them you identify as a female, you'll get in.

Hey SoulAdor ! We have scholarships for both men and women and we post about them regularly on Codeforces! If you are interested in one, you can apply on our website! Everyone applying to the university is taken into consideration for a scholarship and no separate application is required.

This is why you're blue xD

good luck

Problem difficulty. Div. 3 problems are generally easier than Educational rounds.

flush the print. You can read the linked page, given in problem.

I think E is related to finding the inversions in the array but couldn't improve the time complexity from O(n^2)

For E: Fix l, starting from 1 to x. The idea is similar to 2 pointers and you will need some precomputated arrays.

Precalculate p[x] = are numbers <= x sorted, s[x] = are numbers >= x sorted, l[x] = max number <= x, f[x] = min number >= x, you can check if (l, r) is good in O(1), just do binary search.

F is just counting the coefficient of each $$$b_i$$$. You can process the $$$b_i$$$'s in sorted order and use a BIT to efficiently count how many terms smaller than your current $$$b_i$$$ are in a range, and their contribution to the coefficient.

Here you are: 54185189

code for B

The queries are a1*a2 a3*a4 a1*a3 a5*a5，It is possible to deduce a1 a2 a3 a4 from the first three queries and we got a5 by asking a5*a5, Then the array can be determined uniquely.

I was thinking on similar lines but wasn't that n^2 logn? How fast do you test if a particular l,r is valid?

Check answer for $$$a_{1}$$$ and next 4 elements, $$$a_{1}$$$ is equal to GCD of query answers hacked

Ask four queries: a1*a2, a2*a3, a3*a4, a4*a5

brute force all 6! = 720 permutations, and check if the it matches with the above.

https://mirror.codeforces.com/contest/1167/submission/54187357

Ask (a1, a2), (a2, a3), (a3, a4), (a4, a5). Since ai*aj are unique you can get first 5 values easily, and the remaining value is a6.

Test cases visible now

10 1000000 404504 367531 741030 998953 180343 781888 161191 855804 689526 976695

Input/Output speed is not a problem because I also used cin/cout in E and pased. You just need to add ios_base::sync_with_stdio(0) to make cin/cout as fast as scanf/printf.

Because adding two strings is linear to their length. If you just push the char in the end is O(1). Changing it with += that equals to push_back it gives acc 54211273 (your sub with this change)

Why?

Wrong output

The line producing the error is probably this:

for(i=s.size()-11;i>=0;i--)

s.size() returns an unsigned int and if s.size()<11, s.size()-11 will underflow and take a value of the order 2^32.

For s with length less than 11

dfs

It is Memory limit exceeded

Because according to your method, the fourth and fifth Numbers can switch places

因为你第四个数和第五个数可以换位置拉。

Seems like you don't separate the numbers in your answer (with spaces).

You forgot the & inside scanf

You can also solve it recursively, by using the fact, that all valid sequences S = (A)B, or empty.

54212912

Yes. Actually, you just have to invert the color before processing a '(' and after processing a ')'.

There are O(N) solutions using 2 pointers. However, I think only simple O(NlogN) solutions passed (binary search).

sizeof(vs) is a constant value, you have to multiply it by the size of the array.

Correct command would be memset(vs, false, sizeof(bool) * (n+1)) because type of elements in the array is bool. sizeof (vs) will typically be larger (8 bytes) than sizeof(bool).

vs is a pointer, sizeof a pointer is generally 4 bytes (8 bytes for x64 compilation).

let r0 be the nesting of string with color 0, similarly define r1.

Initially, r0 = 0 and r1 = 0.

now ,each time you encounter an opening bracket, if r0<r1, color this bracket 0 (also increment r0)else color this bracket 1 (also increment r1).

Similarly, each time you encounter a closing bracket, if r0>r1, color this bracket 0 (also decrement r0)else color this bracket 1 (also decrement r1).

This guarantees that both strings will be balanced bracket sequences because r0+r1=nesting of original string =0 and r0 or r1 can't be negative (because we ensured it in the loop above) so r0=0,r1=0.

This also guarantees that max nesting is minimised because only the min is incremented when encountering an opening bracket (always better than incrementing max) and the max is decremented when encountering a closing bracket (always better than decrementing min).

@Radwoosh can you give approach and idea to solve problem D

MikeMirzayanov this is happening again :/

MikeMirzayanov Judge out of order!!

For fixed i, find all j's with (a_i >= a_j), then answer will be the sum of min(i + 1, j + 1) * max(n — i, n — j). Go through i's in increasing order and maintain several fenwick trees.

Save the maximum index and the minimum index of each different elements in a. Then think of how to judge a f(l,r) is valid or not in O(1)

Maybe you are not building the graph in an efficient way. Suppose you have 2 5 7 9 Then you don't have to do

2->5->7->9
5->2->7->9
7->9->5->2
9->2->5->7

Instead do something like
2->5
5->7->2
7->9->5

You don't need to make exact graph as you only have to count connected components.

you can skip visited groups

Lets take first case there are 5 groups and 7 people. Each of 5 rows starts with some number that means how many people in Ith group. For example in first group 3 people with number 2, 5, 4 and so on. And problem says if person sends news, their friend can also send info to their friends. After this if person in this group he can share news to this friends and if this friends in other groupes they can share news to other friends in that groupes. At the end we can say that we need to find every component and people in this component can share info with this size of component(including himself). First case if we take person with number 1 he is in two groupes {1, 2} and his friend 2 is in group {2, 5, 4} and if we add this two groups its {1, 2, 5, 4} everyone can share new with themselves that means 4 is the component size. You can solve this problem with dfs or dsu)

That is true but not enough. For example, leaving one element only inside leaves array sorted, if l != r, then we can leave l + 1

You are assigning the value of c to val[i] while running dfs, c being the number of connected components, this doesnot ensure that the parent of all these components is 'i' and therefore the answer is coming out to be less than than the actual number of components. Just a little bit of change and there you go..!!! 54225792

PS-- This might give you TLE in system tests as you have not used weighted dsu.

You're right. This is my first interaction problem.Wish you can be blue name

I think you will :)

congratulations！

Because he used a technique called 'Path Compression'.

In his code

int fin(int v)
{
  if (v!=oj[v])
    oj[v]=fin(oj[v]);
  return oj[v];
}

not

int fin(int v)
{
  if (v!=oj[v])
    return fin(oj[v]);
  return oj[v];
}

So after a fin(v) operation, the nodes on the path from v to the root will all directly connect to the root.Therefore, when you perform fin(i) (i is a node on the path from v to root) will just return oj[i]

dont tell me what to do

same for me.
then I used dfs and it got ac.
I don't know what is the mistake.

I also got WA test 3. You should check in your connect function that you don't connect the same element.

The answer is the same for vertices in same connectivity component. You dont need to clean the array.