Блог пользователя HolkinPV

Автор HolkinPV, 12 лет назад, По-русски

Всем доброго времени суток)

Рады приветствовать вас на очередном раунде Codeforces #151 для участников Div. 2. Как обычно, остальные могут поучаствовать в нем вне конкурса.

Задачи для вас были подготовлены авторами: Павел Холкин (HolkinPV) и Геральд Агапов (Gerald). Традиционно хочется поблагодарить Михаила Мирзаянова (MikeMirzayanov) за прекрасную систему Codeforces и Polygon, а также Марию Белову (Delinur), которая перевела условия задач.

Распределение баллов по задачам будет стандартным.

Всем участникам соревнования мы желаем удачи, успешных взломов и высокого рейтинга!

UPD: контест завершен, надеемся вам понравилось)

Поздравляем победителей:

  1. a58 (решивший все 5 задач)
  2. thangpc
  3. Minecraft
  4. xiaoshua3
  5. Noskov

UPD2: разбор задач можно найти здесь

  • Проголосовать: нравится
  • +98
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +46 Проголосовать: не нравится

Can you please fix the registration for Div.1 participants? We can't register out of the competition.

»
12 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

lets fun everybody :)))

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    we want to register , watching others writing contest isn't very attractive :))

»
12 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Div1 people are unable to register for the contest (unrated). Please fix this issue.

»
12 лет назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

We are very lucky div2 participants. Sorry for you(div1) :D.

They will fix it,I am sure. Because many people wants it.

»
12 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Fix please :D can't not wait until succesful register message appear :))))

»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

all contestmakers are offline :(

»
12 лет назад, # |
  Проголосовать: нравится +68 Проголосовать: не нравится

I guess if Div 1 registration won't be fixed soon, there will be more new users than usual in this contest.

»
12 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Good Luck everybody!

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

maybe everybody wants to be easy hacks :D

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

Don't worry, some of the contest authors will connect before the contest start because they have to check everything is ok, and they will fix it.

»
12 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

REGISTERED!!!

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

151 minutes before the start Codeforces Round #**151**,Good Luck everybody!

»
12 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Thank god! I has just register succesfull :))

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Lucky codings and hackings to everybody ;) Just Have Fun!

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Lucky codings and hackings to everybody ;) Just Have Fun!

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

    sorry to say,but I don't like when someone says "wish you successful hacks",Simply say that I wish you success,sorry again if I said something bad,This is only my opinion.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +21 Проголосовать: не нравится

      "wish you successful hack" it is not bad wish. It means you help someone who coded wrong to know that his/her solution wrong! If he/she didn't locked that problem he/she will resubmit it. Otherwise if he/she already locked that problem wil not wait for that problem while judging.

      If someone didn't hack your problem while you submitted wrong solution. You will think your solution is acceptable

      Hacker gain 50 more point for their goodness ;)

      • »
        »
        »
        »
        12 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

        Yup! I think so

        Just imagine that you submit, accept pretest but WA in the main test

        You may wish that somebody hack your solution and you will recheck your submission :)

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Стандартная разбалловка — это замечательно. Правда, давно уже не было динамической, хочется верить, что она в процессе доработки.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Думаю контест будет решаемым) Всем удачи!!

»
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

gl & hf

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

good luck everybody, happy solving! :D

»
12 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Hope server will stable today.

»
12 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится
Комментарий удален по причине нарушения правил Codeforces
»
12 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

I liked the problems, but they seem much easier than usual div2... Hope I am wrong and my solutions will fail full system test =D

Edit: nevermind, just figured out that my E solution is a complete failure. :D Edit2: YEAH! E failed with Time Limit on 60 =D

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    You should not talk about your solutions during the contest: you give a advantage at the coders who are on the same room than you and who came here by saying that your E, if it isn't some bluff, has chance to be hacked.

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      that's why I'm not even going to unlock it.. =D Anyway, I didn't say anything clear about it...

»
12 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

Could anyone explain it to me please:

Q(k) = {cu :  cu ≠ k and there is vertex v belonging to set V(k) such that nodes v and u are connected by an edge of the graph}.

»
12 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

Раунд действительно такой простой или всех покрашит на систестах?

»
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Nice contest.

»
12 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

По-моему E с ВКОШПА прошлого года...

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    а как решалась то?

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Храним для каждой вершины дерева deque<set>, где в deque[i] хранятся айдишники всех имен на глубине i. В dfs-е предок забирает информацию у потомков, сливая все элементы меньшей деки в большую, а потом добавляя в деку спереди сет с единственным элементом — id текущей вершины.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Я думал что подобная штука не пройдет, там же около квадрата памяти?.. Или вся фишка в "около"? :)

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

          За счет того, что мы всегда сливаем из меньшей деки в большую, операций и памяти будет в худшем случае N*log(N). Ах да, деки надо выделять динамически, тогда предок будет забирать всего лишь указатель на самую крупную деку у потомков.

          Забавно, что там по пути надо сеты объединять, и там тоже в сумме мало операций.

          В общем, вот код.

          Да, по хорошему сеты надо тоже указателями хранить и сливать из меньшего в больший, я как-то забил на это и оно все равно прошло систесты... Может, не критично?

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Понял, спасибо)

            Я тут подумал — "тупое" решение с линией времени на запрос прошло претесты (потом, разумеется, провалилось на полном тестировании), отсылал просто так, от скуки, хотя контртест к этой штуке очевиден. А что, если бы кто-то из правильно решивших заблокировал свое решение? Тогда мне бы ничего не мешало заблокировать свое, терять то все равно нечего, и посмотреть \ закодить его идею, благо времени еще много оставалось. Скриншот сделать, например... Такое разрешается правилами? (in before — такое не проверить)

            • »
              »
              »
              »
              »
              »
              »
              12 лет назад, # ^ |
                Проголосовать: нравится +1 Проголосовать: не нравится

              Так во время контеста отослать-то нельзя, если уже заблокировал. Только после контеста. А после контеста и так можно смотреть все что угодно.

              • »
                »
                »
                »
                »
                »
                »
                »
                12 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                Ааа... Неправильно понял диалог вверху топика. провал.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Нет, она не такая, там надо посчитать не просто количество, а количество с различными именами.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

in how much time are the systests completed???

»
12 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Can we give input with leadings zeros when it must be integers? I have seen a scanf("%i") on my room, but didn't know if I can hack him by giving integers like 033 who will be considered like a hexadecimal.

»
12 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

in how much time are the systests completed? EDIT: So, much negative votes just for asking a question!

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

Задача D самая легкая, по-моему)

Упс, забыл посортить вектора перед выполнением unique. Гробище, невозможно сдать.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Я тоже не понимаю, что эта задача делает под буквой D. Я час просидел над C, так и не придумав нормального решения. Сдал какую-то чушь. На прочтение задачи D у меня ушло минут пять, зато потом считанные минуты чтобы написать тривиальное решение.

    Аналогично с задачами A и B. Я трубашатал эти коды глазами парсить. Там, оказывается, цикл начинается от i, а не от 1. Для меня такие тесты на внимательность всегда были губительны. Зато задача B уходит за 3 минуты, 2 из которых ушли на чтение условия.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    А я написал решение, забыв, что нужно обязательно выводить существующий цвет. Потом 30 минут сидел и не понимал, на каком таком тесте падает решение. Гроб, а не задача.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    а я решил написать дфс по графу и забыл, что он может быть несвязным=)

    может задумка авторов была в том, что в д все бросятся писать граф, как я, и словят или тл или еще какие гадости, а более простое решение, которое бол-во сдавали, не увидят.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      Можно же без дфс'а : храним для каждого цвета вектор вершин, у которых такой цвет, а потом втупую перебираем вершину, берем ее цвет (если до этого не обрабатывали), и проходимся по вектору этого цвета, попутно просматривая соседей каждой из вершин и проверяя их цвета. Заходит за 218 мс.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Да, я примерно так и придумал, после того как залил) Я с Ц долго провозился и на Д мало времени осталось, поэтому в лоб решал, лишь бы успеть закодать=)

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        А я тупо хранил при помощи map<int,set > множество всех разноцветных соседей для каждого цвета...

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится

          "Кто как извращается" (c)

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

»
12 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Wow Amazing system testing speed.

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

In question D , the definition of Q(k) was quite mathematical , I could not figure it out correctly so got a lot of wrong answers.

»
12 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Вот смотрю я чужие решения С и... Мне кажется или куча народу при решении вслепую тасовала возможное количество солдат и потом проверяла, можно ли их послать?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    ага. мой random_shuffle() и просто проход с начала пока не встретим сумму, которой нет в сете, прошел. там очень маленькое ограничение на k, поэтому легитимно

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      У меня даже без random_shuffle() какая-то фигня заходит.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится

        А зачем рэндом, зачем фигня? Выведем каждого солдата по отдельности. Потом выберем самого красивого и выведем с ним вместе каждого из оставшихся. Потом выберем двух самых красивых, выведем каждого из оставшихся вместе с ними. И так далее. Очевидно, что из-за монотонности это будут различные суммы. А их количество — n+(n-1)+(n-2)+...+1=n(n+1)/2.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Можно было и без этого решить ведь Оо

      Вести массив с различными возможными суммами и массив массивов с различными возможными ответами. При получении нового значения пробовать добавлять его в конец всех имеющихся возможных значений и проверять, допустимо ли такое значение. И такие действия проводить пока количество имеющихся возможных ответов достигнет к.

      P.S. Хм... Я в Д вместо цветов считал соседние вершины другого цвета, на чём и зафейлил. =(

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Оказывается заходит полный рэндом. Т.е. храним в set полученные суммы, и пока не набрали нужное количество, берем случайную n-битную маску, считаем сумму соответствующего подмножества, смотрим в сете, была ли такая сумма.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    А я делал что-то типа рюкзака: хранил в мапе текущие набранные суммы и пытался к ним добавить очередного солдата)

»
12 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

perhaps it was better if problems C and D were swapped, for a more standard score distribution!

»
12 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

this contest was very good, one time it is difficult an one time it is fun :D :)))

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Рандом по С заходит, это так и предполагалось?

»
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

will be the rating soon?? i cant wait, am nervious :D :D

»
12 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Печаль такая, Д прочитал за 7 минут до конца и не успел заслать( А в дорешке зашло( Жалко. Но все равно хороший контест!

»
12 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

What is the main idea of problem C? Though I could managed to make it accepted by randomized algorithm(2616018), but I think it's not beautiful...

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится
    1) n times 1
    
    2) n-1 times 2 (pairs with most beautiful)
    
    3) n-2 times 3 (two most beautiful with others)
    ...
    k) n-k+1 times k (k-1 most beautiful with others)
    ...
    n) all of them
    
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Sorry, I posted my solution in Russian, but forgot to translate it... First step. Let's print every soldier. Second step. We take the "beautiest" soldier and print him with every differrent soldiers. Third step. We take two "beautiest" soldiers and print them with every differrent soldiers. And so on. Obviously, all these sums are different (because of monotony). And thier number: n+(n-1)+(n-2)+...+2+1=n*(n+1)/2. Example of output:

    1
    2
    3
    4
    4 1
    4 2
    4 3
    4 3 1
    4 3 2
    4 3 2 1
    

    Code

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Randomized algorithm, cool =)

    Notice that k is at most n.(n+1)/2 Solution is to use the following values:

    (a[0]),(a[1]),...,(a[n-1]), (contains n detachments)

    (a[0],a[n-1]),(a[1],a[n-1]),...,(a[n-2],a[n-1]), (contains n-1 detachments)

    (a[0],a[n-1],a[n-2]),(a[1],a[n-1],a[n-2]),...,(a[n-3],a[n-2],a[n-1]), (contains n-2 detachments)

    ...

    All of these sums are different. Number of available detachments using this method = n + n-1 + n-2 + ... + 1 = n*(n+1)/2 so you will always be able to get k detachments.

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

    The randomized solution is much more beatiful for me :| I didn't implement it well myself though.

    2619137 — a fixed 50 percent probability was way too slow

    2621963 — a randomized probability makes the solution quite fast

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    There exists a rather simple deterministic solution which has O ( N * K * ln ( K ) ) complexity. Traverse though the array and try to add current number to any of the possible sums and if you can make a non existing sum add it to the list of existing sums. Use a set to check if a sum exists or not in logarithmic time.

    Solution : 2616373

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem D:

Please note, that you want to find such color, that the graph has at least one vertex with such color.

for the sample below

3 1

1 2 2

2 3

my output is 1, it passed system test though there is no vertex with color 1. i m still confused. o.O

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    1 Vertex color is 1.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    you are confusing between vertex color and color of those vertices which are connected by edges. vertex 1 is colored by color 1 and hence it counts.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      vertex 2 and 3 has same color, so they are not "colored" => they have 0 colored neighbours, so as vertex 1 that has color 1. So the answer is 1.

»
12 лет назад, # |
  Проголосовать: нравится -22 Проголосовать: не нравится

ну вы и нубы!!!

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Sorry if this seems to be a stupid question, but why is B's solution, n if sum mod n = 0, otherwise n-1?

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    It's obvious that we always can make n-1 equal by adding or subtracting 1 from any other sacrifice-lamb element (e.g. n'th). If sum mod n == 0 then we can also do this for that last element, making all of them equal to sum div n.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    We can make an unlimited number of moves.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    1. n-1 is always possible: we can make a[2]..a[n] equal to 10000, decreasing a[1] at every step.

    2. If sum % n == 0, we can make all a[i] equal to sum / n. And it's obvious that we cannot make it otherwise.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    when sum%n==0, we can get n numbers, which will be equal to average. when sum%n>0, we can get n-1 numbers, which will be equal to average, and 1, which will be average+sum%n=)

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Thanks all of you.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

it is frustrating to continuously check whether the ratings have changed or not after the end of a great contest...

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Ну почему каждый контест выигрывает чувак который ни разу не писал контест??????

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Да и больше он и не участвует, как правило.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Точнее unrated аккаунт. Чувак может и много раз писал.

»
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Ждем обновления рейтинга

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

plz quiqly :(

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Господа, я глупый. В задаче D на тесте

2 1
500 300
1 2

какой должен быть ответ? и почему. имхо и 500 и 300 подходят, но чекер хочет видеть 300. почему?

»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Banging my head after solving problem C now :| I was using bit-masking and unordered_set in the contest and got hacked (TLE)! It couldn't pass the test cases though,, by the way,, very nice contest. Loved the problems. Tricky yet pretty simple solutions :)

One simple request,, found it bit hard to understand the problem descriptions,, a simple note and easy explanation could help us and save much time of us. Thanks :)

Sorry for my bad English.....

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I think there's room for improvement in the English Descriptions. Anyhow, they're always comprehensible.

»
12 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Печалька, после сдачи первой задачи вырубили свет =(

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is the approach for problem E?

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For E they said that Print m whitespace-separated integers — the answers to Polycarpus's records. But printed integers on new lines.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Actually it doesn't matter, depending on the judge used. When we must print numbers, usually the CF system checks your output token-by-token, ingoring whitespaces and new lines.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

which data structure should we use to find the number of different strings on a segment in problem E?

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    http://codeforces.me/blog/entry/5935

    It's link to AC solution, which do it in such a way:

    1. At first calculate it in linear time.

    2. Cache the answer into some map and in future answer to the same query in O(logN) time.

    P.S. If you would like to read some prove of correctness, look at http://codeforces.me/blog/entry/5935 :-)

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    For arbitrary queries [L, R] your may for each i precalculate next[i] (minimum j > i : a[i] = a[j]), and then answer to query will be number of i in [L, R] such that next[i] > R. In offline it can be calculated in using segment tree with sweeping line.

    • »
      »
      »
      12 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Does it consists of sorting queries or you can get the answer for arbitrary query in o(logN) time ?

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        "In offline" means, if I have m queries, I can get all m answers in time.

        Let our quries are segments [L..R], and array "next" is already calculated.

        for i = 1..N

        1. cnt[next[i]]++
        2. for all q : R=i increase answer[q] by Sum of cnt on [R+1..n+1]
        3. for all q : L=i+1 decrease answer[q] by Sum of cnt on [R+1..n+1]
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          This can be done in o(N+M) time. You are always looking for sum on [r+1..n+1] so you can easyly change it in o(1) when you step to next i.Sum will decrease by cnt[i].and you will go to i+1.Looks like you will get LogN for binary search to transform V[i], K[i] into L[i],R[i].