Zauważ, że nie musisz pamiętać, dla każdego pola, czy było ono zaznaczone. Spróbuj przechowywać jedynie informacje o ilości pionków dla kolumn, wierszy i - jak wpadniesz na pomysł jak - o przekątnych.

Czyli jak dostajesz pole (6,1), to:
kolumny[6]++;
wiersze[1]++;
Możesz teraz przechodzić po kolumnach i wierszach, i liczyć max. W taki sposób otrzymasz złożoność O(q*n*m), gdzie q to liczba zapytań, a n i m rozmiary planszy.


Dla lepszej złożoności, powinieneś użyć formy przechowywania danych, jaką jest std::set.