I have more downvotes than upvotes of this blog

Unfortunately we can't postpone the round, because it is an Elimination Round for Technocup and was scheduled long before.

I don't want delay.

It's clashing with AtCoder Beginner Contest 110 too. :(

Just do both lmao.

First power of two round since 2014!

yes

Better than contests that started at 11:35p.m.

This world needs one more cp platform for Сhinese, Japanese, Vietnamese and Australians.
btw MikeMirzayanov can earn a lot of money by trading his cf system and installing it with Full Construction for anyone who could pay him some amount of money, so that person could hold contests there and get donations.

But ...... many of HE->OIers doesn't have a holiday in Middle Autumn Festival...

It's three in the previous contest.

i think three

I think (div.1 A=div.2 C) ,(div.1 B=div.2 D) ... (div.1 E=div.2 G)

Wait for question to pop up.

The question will have 2500+ submissions within 6-7 minutes, then :P

You are such a liar!!

Don't be angry with downvotes, you don't want Mike to see that. Codeforces community tryin to help you by hiding this comment

Как я понимаю пока только ведутся переговоры с возможными другими площадками. Москва будет точно, другие города — посмотрим.

Все три раунда будут рейтинговыми.

If you go to the contests sections, you can see the duration of every contest (it's 2 hours btw!)

"Mega-Cookoff"

Спасибо, исправил.

I prefer a hack rather than system failure. Since it gives me a chance to correct myself. I always pray that if my solution lacks something, then its better that it gets hacked.

Um... Nobody?

same here

Mine did too when I first read it so I was like "you know what? Convex hull!" lol

I got the convex hull out of the 4 points they gave us on the input and then, for each point, I tried to add it to the convex hull. If this point is in the new convex hull, that means this point isn't originally inside the polygon given (or it wouldn't be in the convex hull).

I mean, I know there's probably a much easier solution, but that's what I came up with in a few minutes xD

Div2 B Write equation of each line then divide rwctangle based on x coordinates and check if y lies below or above the line segments. Also do the case when n-d<d.

Each line on the rectangle can be written as y = x + c or y = -x + c. Finding c for all 4 lines is trivial, as well as <= or >=. For every coordinate see if the inequality is true for all 4 equations.

Look at the picture:

These red lines are covering all of the points of the rectangle.
Now focus on the topmost red line. What is common for all the points that lie on that line?

All of the points on the top line can be descibed by this equality: y - x = 2.

Since the coordinates are small , iterate through all the coordinates which lies on or inside the rectangle and mark them as 1. Now if the point lies outside the rectangle then the value of that point would be 0.

So why you submit it twice if you get ac

I used the int version of popcount... wasted over 1 hour and 5 submissions

Could've been something like

2
7 1

something like

6

17 17 73 73 163 163

answer should be 262158769.

My approach -
Considering the count of 1 bits as elements in the array.
Sufficient condition -
good sum(l,r) has to be even and sum(l,r)/2 >= max element of (l,r). And log2(1e18)<63.
Then iterate until sum(l,r)<=126.
Rest of r with even sum is good. At max 126 iterations.
Time Complexity — O(126*n).

Upd — 128 is loose upperbound. 64 is enough.

I will try to explain my approach, though I failed on test 5 for unknown reasons: - For a certain r, you will store all "records" from right to left, which are new maximum numbers. You can see there are at most 60 values of this. Then you can simply binary search in this range for the rightmost index x that sum(x, i) >= 2 * bits. Then prefix sum in this range is easy.

As you said, you have to have:

1. sum(l, r) is even
2. sum(l, r) >= 2 * max(l, r)

This is easy to prove, since your basic operation is decrementing one from two numbers in the interval (meaning that some of their bits cancel each other out).

But we notice that max(l, r) <= 64, and the value of every element is at least one, so you can:

1. Brute force intervals with length <= 64
2. Count number of intervals that are longer than 64, with even sum

code: 43313078

Thank you all very much!

He didn't solve A, but he solved B, C, D :)) rarai

That's overkill.

At least you failed while being in div1, something i can't say about me.

Happened to me too :(

I think you can set x_i = 1, a_i = 0, b_i = 0, which essentially provides you with a unique first generator state. I think the result for (p_i) = (5, 3, 3, 3) is 31.

"Note that each digit of sequence should belong to exactly one segment."

AFAIK let it's height be h, and base length be b, now 1/2*b*h = n*m/k , so if 2*n*m%k != 0, then print "NO"

else note than you can always get one value of b less than n and one value of h less than m just by dividing gcd's and simple manipulatins

You can construct the triangle using the points (0,0), (a,0) and (0,b) for some values of a and b. The first thing to check is when you simplify the fraction by diving by gcds if the denominator is greater than 2 there is no solution. You can see this because of the shoelace method you mentioned. The key to finding a and b is when you divide by gcds first divide n and k by gcd(n,k) then take this new value of k and divide m and k by gcd(m,k). Then if in the end if your k is 2 your new values of n and m will work for a and b. If the new k is 1 you have to multiply one of these results by 2.

we aren't not allowed to see other's submissions until system pending is done.

But maybe you're missing the case when n*m isn't divisble by k, but 2*n*m is .

I feel like recently it's broken. 1 contest it predicted me having +112 when in reality, it's a mere +55. The second time not as broken, still, +102 turns into a +124.

you must wait until the new year

If you move boxes i ... i + k to positions x + i ... x + i + k, it costs:

We want to choose the x that minimizes this. Note that the function is convex. We also have:

Where comp(x, y) = 1 if x ≤ y, and  - 1 otherwise.

Since the function is convex, therefore the difference is increasing, and cost(x + 1, i, k) - cost(x, i, k) only changes when x = (a_j - j) for some j, we can just binary search the index j where when x = (a_j - j), the change first turns positive. This is the minimum of cost(x, i, k). Then, we just need to calculate cost(a_j - j, i, k).

To do both, we store in a segment tree two values. For an interval [x, y] in the tree, we store:

On the left side of j, the absolute value does nothing, and on its right side, it multiplies by  - 1. Therefore, we can easily calculate the cost.

My solution is O(n log(n)^2), but a O(n log(n)) solution can be easily achieved by doing the binary search inside the segment tree.

Code: 43339602

Обычно проходят 100-150 (в прошлом году было так), ты вряд ли пройдёшь с этого раунда

Even with the different templates the main code is the same and that's definitive proof it's plagiarism

I think it is

"Atleast my rating should be reverted back" "My code is completely correct"

Stop with the trash attitude, you made a mistake, just own it.

Here, i modified your code and it got accepted: https://mirror.codeforces.com/contest/1058/submission/43347029

You had undefined behavior when accessing prefix_sum[pos] when pos = -1, so the output is never guaranteed to be the same.