haha,friend,You are very speedy.

Надо будет зайти в гости)

Подожди меня, нам по пути.

Пацан сказал — пацан сделал.

No, hardly every contest. Count contests per year and think: could there really be so many existing calendars?

what about other rounds you still wish same thing

Since you know that, so it won't be surprising ;)

Ночь, ледяная рябь канала,
Аптека, улица, фонарь.

I was going into BIT ideas, Then I thought that why is GF(2) given, find solution was really cute =D

Div1-A/Div2-C, aka "how to solve a problem while ignoring over half of the input". Pretty nice :P

Чисто за n² + nq не подразумевалось. За (n² + nq) / 32 — может быть. То решение прошло тесты?

Ok, i just solved it.

Stack works when you can't see a hill again after removing it, which doesn't work in this case.

The LCA is correct (that's pretty easy to see). To find the next hill a climber goes to from hill i, you add the points from right to left, remember the top convex hull (well, it's actually a concave curve, but it uses the same idea as convex hull algorithm) of these points, update it when adding points and always pick the leftmost point in the hull so far (after the just added point, from which the climbers go to the next point of the hull). This can be done using vector cross product — as long as the leftmost 2 points of the hull (if they exist) are placed in such a way that the leftmost one is below the line from the just being added point to the one to its right, you remove the leftmost point of the hull — because it won't be in the top convex curve ever again. It works the same way as the standard convex hull algorithm.

Another contest where D appears simpler than C. At least to those who are used to more algorithmic problems — like me :D. Too bad I missed the start of the contest (thanks to the modern world's stupid shopping obsession), I think I could've done well.

And I am probably going to fall at my lowest rating in the last 2 years or so. Last two contests have been miserable for me. Making a lot of silly mistakes, I dont know what has happened. :( T_T . But both of these contest had very exciting problems.

Вывод по одному символу. Такие решения у нас работали по 4 секунды.

раскрой скобки в выражении

там получится что ответом является сумма произведений диагональных элементов

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

Далее будем делать итеративный "подъем" — если наш предок не закрывает видимость на своего предка, то делаем нашим предком предка нашего предка. Иначе останавливаемся. Фактически в задаче от нас требуют выпуклую оболочку — и этот алгоритм проще понять, представив его, как построение выпуклой оболочки.

Понятно, что каждая новая вершина добавит в выпуклую оболочку не более одного ребра, и каждое ребро мы из оболочки выбросим не более одного раза, поэтому сложность такого построения графа — O(N).

cin/cout does usually works longer than printf/scanf...

use read/write instead!

Each operation on cin flushes cout by default. Use cin.tie(NULL); to prevent this.

Чем же подозрительных?

Там нет формулы. Просто если увидеть, что каждое произведение по сути встречается дважды

В итоге получается сумма произведений диагональных элементов, что в свою очередь является просто суммой диагональных элементов. Произведения всех остальных пар производятся дважды и дают в результате либо 0, либо (2 * 1) % 2 = 0, стало быть, их можно не учитывать вовсе.

Очевидно [прямо из условия следует], что ответом на задачу будет

(tr(A^2)) mod 2

По свойству следа матрицы получаем:

tr(A^2) mod 2 = (tr(A)*tr(A)) mod 2 = tr(A) mod 2

UPD: Пояснение здесь

матрица a размера n*n

скобки

(a(1,1)*a(1,1)+a(1,2)*a(2,1)+...a(1,n)*a(n,1))+(a(1,2)*a(2,1)+a(2,2)*a(2,2)+...a(2,n)*a(n,2))+ ...

(a(n,1)*a(1,n)+a(n,2)*a(2,n)+...a(n,n)*a(n,n))

скобки по строкам — отбрасываем(они не влияют)

получаем ситуацию, когда каждая пара произведений (кроме a(i,i)*a(i,i)) встречается по два раза их сумма всегда ноль(1+1=0б 0+0=0) остаются пары: a(1,1)*a(1,1)+a(2,2)*a(2,2)+...+a(n,n)*a(n,n)=a(1,1)+a(2,2)+a(3,3)

Ну а каждое изменение матрицы меняет только одни диагональный элемент. всё

По сути, нам нужно посчитать . Сразу можно видеть повторения. :)

Спасибо... :) Рад, что наш контест в ПТЗ понравился.

Чтобы запретить оптимизированные решения за n² + nq, в общем.

Rating updated just now. +26 :p

global array overflow will not lead to runtime error(if only a little), but local one does. overflowed parts may not be initialized correctly.

UPD overflowed 2-dimensional array will get wrong answer. See the implementation of 2d arrays: the i+1-th row is placed right after the i-th row. So if you write overflow data in i-th row the result is the data in i+1-th row is modified.