chuva.cpp

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 10;
const int MAXK = 250;
array<array<int, MAXN>, MAXN> Marc;
array<array<int, MAXN>, MAXN> v;
vector<tuple<int, int, int, int>> queries;
vector<pair<int, int>> coletores;
vector<int> resp;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
int N, M, K;
int Q;

inline void calcMarc()
{
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            Marc[i][j] += Marc[i-1][j] + Marc[i][j-1] - Marc[i-1][j-1];
}

inline bool OutOfRange(int x, int y) {return (x < 1 || x > N || y < 1 || y > M);}
void bfs(int sx, int sy)
{
    for (int i = 1; i <= N; i++) Marc[i].fill(0);
    Marc[sx][sy] = 1;
    queue<int> qx, qy;
    qx.push(sx); qy.push(sy);

    while (!qx.empty())
    {
        int x = qx.front(); qx.pop();
        int y = qy.front(); qy.pop();

        for (int k = 0; k < 4; k++)
        {
            int hx = x + dx[k], hy = y + dy[k];
            if (OutOfRange(hx, hy) || v[hx][hy] < v[x][y] || Marc[hx][hy]) continue;
            qx.push(hx); qy.push(hy); Marc[hx][hy] = 1;
        }
    }

    calcMarc();

    for (int q = 0; q < Q; q++)
    {
        auto [x1, y1, x2, y2] = queries[q];
        resp[q] += ((Marc[x2][y2] - Marc[x2][y1-1] - Marc[x1-1][y2] + Marc[x1-1][y1-1]) > 0);
    }
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    cin >> N >> M >> K;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            cin >> v[i][j];

    coletores.resize(K);
    for (auto &[X, Y] : coletores)
        cin >> X >> Y;

    cin >> Q;
    queries.resize(Q); resp.resize(Q, 0);
    for (auto &[x1, y1, x2, y2] : queries)
        cin >> x1 >> y1 >> x2 >> y2;

    for (auto [X, Y] : coletores)
        bfs(X, Y);

    for (auto x : resp) cout << x << '\n';
}