Ah, I was basing my observation off of personal experience with the SGI rope. I'm not sure if there's a thread-unsafe implementation that's easily dropped in for competitive programming.

In C++, you can use a rope. It will work in O(log(n)) time for random insertion, albeit with a large constant factor. rope

If you want to implement a random insertion data structure yourself, you can use a splay tree for O(log(n)) amortized insertion. splay tree

A treap would also work. treap

Both treaps and splay trees are very versatile and can be extended to do much more than just random insertion.

There's another method for D that uses the largest square submatrix dynamic programming solution and binary search over $$$n$$$.

Method

Solution (using ranges for the binary search part) 186935611

I didn't read B properly and thought that $$$n$$$ could take on values other than the length of the input. I thought I needed to implement a complicated LCP+Suffix Array method than ran in $$$O(n*log(n)^2)$$$ to greedily compute the minimum number of operations needed to produce the resulting string, which I wasn't able to do during the contest.

Here's my solution which actually computes the minimum number of operations: 185016918

For E, shouldn't it be $$$O(NlogN)$$$ instead of $$$O(N)$$$ since you need to sort the astronauts?

Actually, I got it to work by clearing it via swapping with a temporary empty array. I'm still not seeing where the actual $$$O(N)$$$ bottleneck is though (is it because .clear() is $$$O(N)$$$ each time?), since .erase() and .find() are both $$$O(1)$$$ on a hashset with few collisions.

With swapping: 181154447

But .erase() and .find() should both be $$$O(1)$$$ regardless of hashset/table size. Plus, it TLEs even when the hashsets are cleared by using ={}.

Without using .clear(): 181154447

Is it because unordered_set is returning the iterator after when calling .erase()? Didn't know that it could result in an almost 10x slowdown. Are there any ways to prevent that, or should we simply resort to using gp_hash_table/set?

I think the SGI rope's constant factor is too large to make this useful under most contexts.

https://cses.fi/paste/5f59f9d91a30b1823efeda/

Here's my CSES submission for Cut and Paste which times out with a rope. Your trick requires way more cuts. I don't think it'll ever fit in the Substring Reversals time limits. Granted CSES is extremely strict on time limits, but still.

Yeah, I guessed that the start time function was unimodal and passed, but couldn't prove it.

For problem B I did ternary search over the time selected for everyone to meet and it worked but I'm not sure why.

Code

Here's my greedy solution for problem D, which is much simpler, but I can't figure out why it works..

Mark the area of slimes you have cleared out by keeping track of the left and right boundaries. You begin by expanding toward the left (you take care of expanding toward the right first separately). Either you can reach the end, or you can't. If you can, you win (and print "YES"). If you can't, you settle for going toward the left until you reach the maximum health possible, expanding your territory along the way and then try going toward the right. If you ever fail to expand your territory at all, you stop because it means you'll never reach the end.

Do this again for choosing to go right first.

Now, each step increases your existing territory. But actually, it may take $$$O(n)$$$ time to check whether you are able to reach the end or not since you keep going until you would have fallen to below zero health, which might involve experimentation significantly beyond the edges of the territory. If you only expand the territory by 1 each time but you would be able to reach almost the end if you decided to continue, it might take $$$O(n)$$$ for each expansion for an $$$O(n^2)$$$ algorithm overall. But either the test cases are too weak or there's something else limiting the time complexity I can't think of. I encourage someone to hack me or figure out why this technique works in subquadratic time.

173363257

A pretty optimized $$$O(N*\sqrt(N))$$$ solution will pass for problem C.

173266505

My approach is similar, but it uses partitioning instead of a vector of pairs of vectors.

Our goal, as before, is to prioritize the highest bits to be $$$1$$$. We can know that it is possible to make a certain bit number $$$j$$$ 1 in our result by checking whether the number of values of $$$a_i$$$ such that the $$$j-th$$$ bit is $$$1$$$ is the same as the number of $$$b_i$$$ such that the $$$j-th$$$ bit is $$$0$$$.

This allows us to match $$$b_i$$$ with a $$$j-th$$$ bit of $$$0$$$ with $$$a_i$$$ with the $$$j-th$$$ bit of 1 and vice versa. We'll move both such values to the very front of their respective arrays using Hoare's Partition Scheme. For future less significant bits, we can use the same algorithm to rematch values within their partitions to preserve the higher bits we have already used. If we discover that any individual partition for a certain value of $$$j$$$ cannot be matched, we advance to the next value of $$$j$$$.

Now all we need to do is to keep track of the order of the partitions as we make them, which can be done with a set.

Code

Total Complexity: $$$O(N*log(N)+30*N)$$$.

I'm very curious about the gnu c++ segment tree... could someone explain how it works and how to use it?