Зашла бы такая асимптотика в 2004?

Глубоко сомневаюсь.

Задача же совсем халявно решается за O(N + MAXK), либо за . Идея такая: возьмем "четвертьплоскость" с левым нижним углом (X;Y). Если мы сможем разместить нашу "четвертьплоскость" так, чтобы строго внутри нее не было ни одной точки, то это даст нам ответ X + Y. Ну так мы можем двигать ее "лесенкой" справа налево, снизу вверх (ну или наоборот).

Если речь о динамике по состояниям (x_i:?) и (?:y_i) с 80М операций с последовательным обращением к памяти — да, в 2004 зашла бы за секунду.

Нагуглил авторское решение за n^2.

Расстроился :(

Ужасно, думаю надо решить за что то быстрое n log n или n sqrt(n).

А тут решение за квадрат. Ужасно.

Нет, не могу

Казалось бы, не сильно сложно улучшить решение до O(n*log(min(n, MAXK))) с помощью дерева отрезков.