TLE in Calcio (Territoriali)

Buongiorno a tutti, sto provando a risolvere “Calcio”, l’approccio è una sliding window, ma è fin troppo lento dopo il quinto testcase. Non ho idee su come approcciare diversamente il problema e scendere di tempo, né ho idea se ci siano altri approcci o se devo ottimizzare l’attuale…

#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>

//l'idea è usare una sliding window con una matrice 

using namespace std;

void solve(int t) {
  int N, M, K, A, B;
  cin >> N >> M >> K >> A >> B;

  vector<int> X(K), Y(K);
  for (int i = 0; i < K; i++) {
    cin >> X[i] >> Y[i];
  }

  vector<vector<int>> griglia(N, vector<int>(M)); //creazione della griglia

  for(int i = 0; i < K; i++) 
    griglia[X[i]][Y[i]]++; //aumento il numero di alberi che ci sono nella coordinata
  vector<long long> valori; 
  //gira correttamente nella griglia 
  for(int riga = 0; riga + A <= N; riga++){
    for(int colonna = 0; colonna + B <= M; colonna++){
      long long momentanea = 0; 
      for(int c1 = riga; c1 < riga + A; c1++){
        for(int c2 = colonna; c2 < colonna + B; c2++)
          momentanea += griglia[c1][c2]; //se ci sono alberi nella zona del campo li aggiunge 
      }
      valori.push_back(momentanea); 
    }
  }

  cout << "Case #" << t << ": " << *min_element(valori.begin(), valori.end()) << "\n";
}

int main() {
  // se preferisci leggere e scrivere da file
  // ti basta decommentare le seguenti due righe:

  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);

  int T;
  cin >> T;

  for (int t = 1; t <= T; t++) {
    solve(t);
  }

  return 0;
}

L’approccio va bene, però il tuo algoritmo ha complessità \mathcal{O}(NMAB) dovuta al fatto che controlli \mathcal{O}(NM) rettangoli e per contare gli alberi in ciascuno ci metti \mathcal{O}(AB).
Sul numero di rettangoli da controllare non puoi farci molto, ma esiste forse una struttura dati che ti permette di contare gli alberi in un rettangolo in \mathcal{O}(1)?

Forse una mappa…? Associo a ogni coordinata il suo numero di alberi e poi lo ottengo in O(1)…? Credo possa essere questa la risposta…?
Perché set, stack e queue avrebbero il medesimo tempo di un vector, solo la mappa penso potrebbe essere più veloce, anche se enormemente dispendiosa di memoria.
Però come potrei ottenerlo comunque in O(1)? Devo sempre ottenere il singolo di ogni coordinata e sommarlo…

No non parlo di una struttura della STL. Come dici tu il problema è che devi sommare il numero di alberi di ogni coordinata di un rettangolo, quindi bisogna trovare il modo di evitare questo passaggio. La soluzione è tenere una matrice 2D (detta delle somme prefisse) grid tale che grid[x][y] abbia come valore la somma degli alberi nel rettangolo [0, x) \times [0, y). Questa matrice può essere costruita in \mathcal{O}(NM) e poi per contare gli alberi in un rettangolo ti basta controllare solo 4 elementi della matrice grid, qualunque sia la dimensione del rettangolo.

Mi hai appena svoltato la situazione. Non ci avevo pensato ad adoperare una matrice come prefix sum, è geniale. Ora tiro fuori un modo di implementarla, anche se non ho ben chiaro perché mi basterebbe controllare solo 4 elementi della matrice…