Hello everybody!

Now the winter SIS (Summer Informatics School) is taking place, and we, as part of the parallel A*+ with its teachers, have prepared a complete Codeforces Round.

The round will happen at Jan/05/2020 17:05 (Moscow time) and will last for 2 hours. There will be 6 problems in each division.

The tasks of the round were invented and prepared by ismagilov.code, devid, Volkov_Ivan, Jatana, karasek, polinarria, cookiedoth, AlesyaIvanova, KhB, AliceG, D.Pavlenko, VFeafanov, LordVoIdebug, forestryks, Ilistratov, seiko.iwasawa, senjougaharin, Drozd_off under the guidance of teachers PavelKunyavskiy, VArtem, meshanya, budalnik.

Thanks aneesh2312 MarcosK Stepavly Infinity25 tourist antontrygubO_o isaf27 fedoseev.timofey, Kurpilyansky, vintage_Vlad_Makeev for testing!

And, of course, thanks to MikeMirzayanov for great systems Codeforces and Polygon, and 300iq for round coordination.

Good luck everybody!

UPD:

In problem E an error was made in the intended solution, an overflow of long type while calculating the answer. The first test, on which it happened, reached 4 participants (ainta aid Um_nik ecnerwala), among who two passed the pretests, and two others did not, though they should have. In automatic mode, it is not possible to test so that both answers are accepted, because the overflow changes the tests because of the way the requests are encrypted. So, we decided to test two pretest solutions on the old set of tests and the rest on the new one. As a result, three of the solutions passed the tests (congratulations!), and one received WA80 on the 17th answer inside the test, which is clearly not related to the overflow problems. Only the solution that takes into account the overflow problem can be used in upsolving.

UPD: Editorial!

The MEX Foundation Contest #1 (supported by AIM Tech) that was held in the 37th Petrozavodsk Programming Camp now available in the Gym.

The authors of the contest are Jatana, cookiedoth, Egor.Lifar. The problems are of a good quality, a number of participants can approve it.

Special thanks to vintage_Vlad_Makeev for useful advices, LHiC for testing the contest, vintage_Vlad_Makeev for inspiration and AIM Tech Members for the problem review.

Hello, I would like to introduce the plugin FastOlympicCoding for Sublime Text.
It provides several useful features for competitive programming.

I invent method to merge two cartesian trees with maybe intersect keys. And want to know what is asymptotic of it.

method:

let's add to a standard cartesian tree field musorka

struct Node {
  Node *l = NULL, *r = NULL;
  int key, priority, cnt = 1;

  Node *musorka = NULL;
}

and when we want to merge trees A and B A->musorka = B

then write push

void push(Node *node) {
  if (!node->musorka) return;
  push(node->l);
  push(node->r);

  pair<Node*, Node*> spl = split(node->musorka, node->key);
  pair<Node*, Node*> spl2 = split(spl.second, node->key + 1);
  
  if (spl2.first) {
    node->cnt++;
  }

  node->l->musorka = spl.first;
  node->r->musorka = spl2.second;
  node->musorka = NULL;
}

then add this push to merge and split.

Maybe someone can estimate asimptotic of this or give counter test where it works n^2?