Bad luck. Solution for A and C was correct. If these two got rated then.... Alas! they got skipped.

I upvoted you bro....now see my downvotes!

It means "extremely wonderful". :)

It's supercalifragilisticexpialidocious

Even though the sound of it is something quite atrocious

If you say it loud enough, you'll always sound precocious

Supercalifragilisticexpialidocious :)

https://www.youtube.com/watch?v=tRFHXMQP-QU

Yes, you should register in Div2 contest. However, you should not ask if the contest is rated unless you want to get -2137 contribution.

0w0

[deleted]

Are you serious? ._.

You can read more in Wikipedia, but feel free just to enjoy the problems without such background knowledge.

before your comment I was thinking I'm the only one.

There won't, enjoy :)

You just did.

Give me 50$ or I will tell Cristina what you said

Good news for hacker :(

"few" means "not a lot", "a few" means "some", so in fact wishing few bugs is wishing well, while wishing a few bugs is wishing bad.

Hope this contest goes well!

I am not sure, but looks like it was fixed(I tried refreshing 20 times).

This is experienced by some contestants. We're working on this, please go on to other problems first. Sorry for the issue.

same issue here, and i am 90% sure i can't solve any of the other problems. also i am 100% sure the code i am trying to hack is incorrect. :-(

EDIT: after refreshing about 20 times, i was able to successfully hack the above mentioned code. :-)

This contest looks to be difficult

This happened to me in contest 429. Nothing came of it.

I also think so, I couldn't even understand statements of c, d and skipped to E(Hope it passes though, or I will get -200 rating change).

Pretest 3 on C is k = 0.

Your code prints nothing but it should print a single character :(

rip rating too , hate geometry so much :C

sort

for horizontal , consider the point to be at ( - t_i, y_i)
for vertical , consider the point to be at (x_i,  - t_i)
Now consider each diagonal (Same x + y) at a time
Only points among the same diagonal will collide and each point's direction will alternate after each collision.

First notice that instead of looking at time the person starts, you can simply set their x/y coordinate to -t (depending on what way the person is facing). Then notice that instead of imitating a collision, you can just swap the indexes of the people colliding, since they just swap trajectories. Then also notice, that you can place people in buckets based on the sum of their x and y coordinate (people with the same x+y go into the same bucket). In those buckets, every vertical person will collide with every horizontal person, and vice versa. Now, next thing to notice is that every horizontal person will hit vertical people in the order of their x coordinate. Therefore, the last index that carries that trajectory will be the index of the furthest right vertical person. Yes, there's a lot of noticing in this task. At this point you could probably implement it, but there are a few more things to notice if you want to have a nice, clean implementation, but I don't know how to explain what I did, so I'll leave it as practice (if someone really wants to I can try to explain)

Also, cyand1317, I absolutely loved this task, thanks!

Edit: while I typed this someone already answered. I hope this will still be helpful to someone!

Well, wasted too much time on D.

I think this guy is cheating

i got tle with something like n*sqrt*log lol. used sqrt decomp on queries

Nice idea, I see what you did there.

Yes 29985009

Suppose a dancer travelling vertically having position Xi and wait time Wi, and a dancer travelling horizontally having position Yj and wait time Wj meet at time T. Hence,

(Wi + T) = Yj and (Wj + T) = Xi

This will be used to check collision condition and time.

(Xi - Wi) = (Yj - Wj) and T = (Xi + Wj)

Now, sort dancers travelling vertically by Xi and dancers travelling horizontally by Wj. Store dancer indices for each distinct difference (Xi - Wi) and (Yj - Wj) for each type of travellers.

For one particular difference, consider 2 vectors, 1 of horizontal travellers and 1 of vertical travellers, each element of 1st vector will intersect with each element of 2nd vector. Final positions of dancers from these 2 vector will just interchange among themselves independent of other dancers.

Collision happens in sequential order. That is i from vector 1 will intersect with j1 and j2 from vector 2 in order of j1 and j2, same holds other way.

This sequential order can be used to decide final position of each traveller of these 2 vectors combined in O(n). You just need to traverse these 2 vectors in particular order. Sorting the travellers takes O(n * log(n)) time.

Code

Don't, it was pretty hard (IMO).

You can group the people, so in one group all possible collisions happen, and no collision happens between groups. You have to group by p_i - t_i. The previous statements can be proved, for same and different p_i - t_is. After that, you can solve the problem for one person in O(1). I'll leave that thinking to you :)

Let's change find sum of max-min into sum of nxti-i where nxti is next element with value equal ai and nxti <= r. Now it's a very standart problem, I did it with bit and sqrt decomposition

a => 0 aa => 1 aaa => 3 aaaa => 6 ... a(n) => (n)*(n+1)/2

16 = 10 + 6 => aaaaa bbbb 12 = 10 + 1 + 1 => aaaaa bb cc

First, we'll find the minimum accumulative cost of a string. In fact, we will prove something more: the accumulative cost of a string doesn't depend on the order they are combined.

Imagine that between every pair of identical letters, we have a tune. Thus for example, in the example string abababab, each pair of a's have a tune between them, and so as each pair of b's. That's a total of 12 tunes. We claim that the accumulative cost is simply the sum of all tunes.

To do so, we will remove a tune at the moment that the pair of letters are merged into the same string. For example, when we merge aba and ac, the two pairs of a's (pick either a in aba, and pick the a in ac) will lose their tunes (the pair of a's formed by taking both a's in aba has already lost its tune). It's obvious that each tune is removed exactly once, since at the beginning no letter is in a string with any other letter, and at the end every letter is in the same string. It remains to show that each tune does contribute exactly 1 to the accumulative cost.

Consider f(s, c) × f(t, c). Look at each occurrence of the character c in s, and another occurrence of the character c in t. They have a tune between them (because they haven't been merged). There are f(s, c) × f(t, c) ways to pick this pair of c's, and so f(s, c) × f(t, c) tunes as well. All these tunes will be lost when they are merged, and it costs the same amount to merge them. Summing over all c proves the claim.

Now that we have shown that we can compute the minimum accumulation cost of a string from just counting how many times each character appears. If there are n of a character, then they have tunes among them; simply sum over all characters to obtain the accumulation cost.

Now, constructing a string is easy. Just take n as large as possible while keeping ; now we have n a's. Subtract k by and set that as the new value of k. Take n as large as possible again; we have n b's. Repeat until we're done. For k ≤ 100000, it can be proven that this greedy strategy works (it's impossible to have k > 0 after using all 26 letters).

Am I the only one who thinks like "I saw many problem such like this, but I always couldn't come up with idea on this type of problem (simple range query, but also update) so I can't solve this." ?

It's no rocket science to realize that nlg^2n will pass :D

we are in div 1 :(

Me too. I was feeling so stupid the whole time.

yes, it turns out that the order of merges don't matter, and we can consider merges of different characters separately and sum at the end so this approach works. The proof of the above claim stems from the identity

maintain a map of slopes.

Hope my solution doesn't FST...(upd: Passed System Test!)

For any two points i, j that a_i = a_j, if there doesn't exist i < k < j that a_i = a_k, then we create an interval [i, j]. The query just asks the sum of lengths of all intervals that lie in [l, r], and update changes O(1) intervals.

Let's take an interval [l, r] as a point (l, r) on the 2D plane, and its weight is r - l. A query [l, r] asks about the sum of weights of all points (x, y) that l ≤ x, y ≤ r.

You can write a DS that supports add/delete 2D points and 2D rectangle sum query. I used Fenwick tree + balanced search tree. The time complexity is and space complexity is .

As long as you know how to code 2d segment trees, it is. Consider the points of coordinates (prev[i], i) with values i — prev[i]. In one query (L, R), you're interested in the sum of the values of the points with L <= x and y <= R. When you modify a value, at most 3 prevs change

90 lines only 29981295

fenwick tree is superfast and it was likely that it would get accepted (and it did :)))) btw, even n sqrt log with fenwick gets accepted here
so i think there was no reason to get nervous as TL was pretty big

Yes, int = 2^32 = 4*10^9

If you do all operations without double, then long long is safer.

Don't worry, you are safe:) your new rating is 1916

Div2a
6
1 0 1 0 0 1
Answer is no.

For Div-2 A, even this code (surprisingly) passes Pretests, so ez hack is: n=3 and a=[1,3,4].

In problem A my code passed pretests without handling the n=1 case. (Luckily I noticed before getting hacked)

shake it! by emon(Tes.), and Hanairo Biyori by Natsume Chiaki

I think it won't work because "minus nxt[i]-i the rightmost elements of each values" don't really match with red[i]. (didn't see the implementation, so I might be wrong)

Python should be able to perform around 10⁷ arithmetic operations in 2 seconds. Your solution might be inefficient. (For example, did you know concatenating strings is ? If you concatenated so much, your estimation of the number of operations might be off. It might be something like that.)