Yes

They did that. I think you would be one of those people (who are going to Div 1 after rating update) :D .

Hope it will be not mathforces round

yes

Well, last time it was at least four.

It's EarthDay, man

IMO "a segment" phrase has meaning close to "some segment", which is technically any segment

"Two ways are considered different if and only if a segment is painted in different colours in them." means "Two ways are considered different if and only if (at least)a segment is painted in different colours in them."

The phrase "if and only if" is used to declare a coimplicative relationship. That is, ways are considered different if (condition), and only if (condition) they are considered diferent (if (condition) is not satisfied, they aren't different). Its meaning is not related to "only one segment".

I think you need to print output with enough precision.

printf("%.8f",ans) >> WA printf("%.12f",ans)>> AC

Costed me one WA.

B?

My hacks for Div2A. I managed to make 8 hacks in total. That includes hacking 3 people twice... Here my tests with correct answers.

6
Y?C??C
Yes

3
Y?C
No

2
YC
No

3
Y?Y
Yes

100
????????????????????????????????????????????????????????????????????????????????????????????????????
Yes   (Forces TLE)

1
?
Yes

2
?C
Yes

Lo_R_D why Wrong answer : 0 ?

How to paste image?

Mine too.. I'm confused..

Yes, this happened with me too in some previous contest but it got counted.

(X[i] * V[j] — X[j] * V[i]) / (X[j] — V[i]) <=W

You can divide each speed by W, thus getting X[i] * V[j] — X[j] * V[i] <= X[j] — X[i]

X[i]/(V[i]+1) <= X[j] /(V[j]+1)

and the same for >= -w :)

my idea was to find what will be the time taken if wind speed is -w and w and then if 2 planes can meet than time taken by one plane will be more than second for +w wind speed and less for -w wind speed.

Let t(i, v_air) arrival time for v_air airspeed. If direction is same, it holds when x_i < x_j AND (t(j,  - w) ≤ t(i,  - w) OR t(j, w) ≤ t(i, w)).

This reduces to finding a pair i < j such that x_i < x_j, y_i < y_j, z_i < z_j.

Sort by x-coord, and do divide and conquer. Let L a set with X_i ≤ M, and R a set with X_i > M, then we should find a pair such that . This can be done with binary indexed tree. Thus, T(N) = 2T(N / 2) + O(NlgN) = O(Nlg^2N)

You can get minimum and maximum arrival time for each plane.

Then they can arrive at the same time (if they go in the same direction) iff one [mintime,maxtime] is included in the other.

I didn't manage to count inclusions in an acceptable time during the contest though.

For each plane create a point (x_i, v_i). Sort all points by angle around point (0, w) and point (0,  - w). You get 2 permutations of points a and b. You need to find number of pairs of points such that in a the first point comes before the second and in b the first point comes after the second. It's the number of inversions in a^- 1b, which is a classical problem. You also need to handle the cases when 2 points have the same angle accurately in the comparator.

Unable to see submission.

It really impacted some participants including me. I checked my solution of Problem C during the long queue.And finally I didn't have time to code Problem D which I think I can solve it during the contest.

if the wind power is -w and two plane meet at p1<=0 && if the wind power is w and they meet at p2>=0 then they are counted

Cant See your solution now but I did the same thing. Hope i pass the sys tests. Did you handle the case of -1?

Noticed my mistake. I think in this case I should fix all index i, not k.

Corner case:

4 10000 1 10 11 15

My solution answers: (15-10)/(15-1) = 0.357142857

Expected: (15-11)/(15-10) = 4/5 = 0.8

use long long instead of int

For me it was int overflow.

Problems were nice, but this doesn't seem good. Almost same amount of people solved ABC.

Go to hell GreenGrape is the best problem setter ever, everyone makes mistakes sometimes your mother for example

hint : you can draw a line between 2 already drawn lines.

Don't add any new marks until you need to. Keep track of the records where you didn't create a new mark.

Take this case: 0 0 0 1 0 4

Before we see record of 4, ans should be 1. We only created a mark for the first 0 and the 1. Then we know we didn't create any new marks for the second, third, and fourth 0. Now when we see record of 4, we know we need to add 2 new marks on the previous records (not including the current 4).

Now insight is that we should greedily add marks to the most recent records where we didn't create any new marks. This is because if we add a mark for some record, all records after it no matter what will have to contribute +1 to the answer. So we should add marks to the third and fourth 0. Adding mark to third 0 increases ans by 3 and adding mark to fourth 0 increases ans by 1. Now we can create new mark for the record 4 below all other marks, and will satisfy the condition of 4 marks above it. Thus ans is 5. Note that now we should get rid of third and fourth 0 from our list of where we didn't create any new marks.

Since each record creates a mark at most once, complexity is linear.

Maybe a little confusing, I can elaborate more. Also disclaimer I haven't passed sys test.

Edit: passed

you can keep track of the minimum number v of marks that appear after day i.

You know that they are non decreasing, so you can build them from left to right as you read the vector.

Then you need to go from right to left and make sure the increments of your list are at most 1 per day.

With v and m, you can get the minimum number of underwater marks for each day.

How to color 0 unpainted segments in two different ways?

i think the concept behind this is the problems that have multiple solution, so if one can't trace his solution he can submit it and see if it's right or not in the first case

In order to give some mercy for people which submit wrong files, for example from different directory.

It's O(n)

Um_nik is great.

MikeMirzayanov or KAN if possible can you please look into the matter and make necessary changes thank you:)

'P.S. My submission which got TLE on test 7 now passes ...'

You submitted it with different version of compiler

I'm sorry, but in test 22 answer is -1. It's impossible that the answer is zero in this problem, because all the energies are distinct

Wow your submission passed in 998 ms :)

They said that t-shirts will be sent after vk cup final