53682023-04-26 16:40:02zsomborHegyi levegőcpp17Time limit exceeded 0/1003.104s115388 KiB
#include <bits/stdc++.h>
using namespace std;

int n, m, q, x, y;
vector <vector <int>> h;
vector <pair<int, pair<int, int>>> srt;
vector <int> p(5e5, 0);
vector <int> sz(5e5, 1);
vector <int> ind(5e5, 0);
vector <set <int>> qi(5e5);
vector <int> ans(5e5, 0);

void fastscan(int& number) {
    number = 0;
    register int c;
    c = getchar();
    while (c < 48 || 57 < c) c = getchar();
    while (48 <= c && c <= 57) {
        number = number * 10 + c - 48;
        c = getchar();
    }
}

int holvan(int a) {
    return (a == p[a] ? a : p[a] = holvan(p[a]));
}

void unio(int a, int b) {
    a = holvan(a);
    b = holvan(b);
    if (a == b) return;
    if (sz[a] < sz[b]) swap(a, b);
    p[b] = a;
    sz[a] += sz[b];

    int A = ind[a], B = ind[b];
    if (qi[A].size() < qi[B].size()) swap(A, B);
    for (int i : qi[B]) {
        if (qi[A].count(i)) { ans[i] = h[x][y]; qi[A].erase(i); }
        else qi[A].insert(i);
    }
    ind[a] = A;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m >> q;
    h.resize(n);
    for (int i = 0; i < n; i++) {
        h[i].resize(m);
        for (int j = 0; j < m; j++) {
            //cin >> h[i][j];
            fastscan(h[i][j]);
            srt.push_back({ h[i][j],{i,j} });
            p[i * m + j] = ind[i * m + j] = i * m + j;
        }
    }
    sort(srt.begin(), srt.end());
    for (int i = 0; i < q; i++) {
        //cin >> x >> y; x--; y--;
        fastscan(x); fastscan(y); x--; y--;
        qi[x * m + y].insert(i);
        //cin >> x >> y; x--; y--;
        fastscan(x); fastscan(y); x--; y--;
        qi[x * m + y].insert(i);
    }
    for (int i = 0; i < n * m; i++) {
        x = srt[i].second.first;
        y = srt[i].second.second;
        if (x && h[x][y] >= h[x - 1][y]) unio(x * m + y, (x - 1) * m + y);
        if (x < n - 1 && h[x][y] >= h[x + 1][y]) unio(x * m + y, (x + 1) * m + y);
        if (y && h[x][y] >= h[x][y - 1]) unio(x * m + y, x * m + y - 1);
        if (y < m - 1 && h[x][y] >= h[x][y + 1]) unio(x * m + y, x * m + y + 1);
    }
    for (int i = 0; i < q; i++) cout << ans[i] << "\n";
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Time limit exceeded3.058s32424 KiB
2Time limit exceeded3.078s32684 KiB
subtask20/19
3Runtime error29ms65392 KiB
4Runtime error25ms65576 KiB
5Time limit exceeded3.062s33380 KiB
6Time limit exceeded3.075s33520 KiB
7Time limit exceeded3.076s34076 KiB
8Time limit exceeded3.082s34120 KiB
9Time limit exceeded3.062s34300 KiB
10Time limit exceeded3.081s34880 KiB
subtask30/20
11Time limit exceeded3.046s34656 KiB
12Runtime error25ms66928 KiB
13Time limit exceeded3.069s35728 KiB
14Time limit exceeded3.072s45584 KiB
15Time limit exceeded3.069s61336 KiB
subtask40/20
16Time limit exceeded3.059s61332 KiB
17Time limit exceeded3.039s86752 KiB
18Time limit exceeded3.065s61528 KiB
19Time limit exceeded3.062s61632 KiB
20Time limit exceeded3.082s61628 KiB
subtask50/31
21Time limit exceeded3.052s60428 KiB
22Time limit exceeded3.053s55512 KiB
23Time limit exceeded3.104s55280 KiB
24Time limit exceeded3.062s55336 KiB
25Time limit exceeded3.072s55444 KiB
26Time limit exceeded3.055s55268 KiB
27Time limit exceeded3.078s55416 KiB
28Runtime error39ms71148 KiB
29Runtime error35ms70900 KiB
subtask60/10
30Time limit exceeded3.068s115388 KiB
31Time limit exceeded3.088s90076 KiB
32Time limit exceeded3.063s90084 KiB
33Time limit exceeded3.068s90128 KiB
34Time limit exceeded3.078s90108 KiB
35Time limit exceeded3.075s90052 KiB
36Time limit exceeded3.072s89876 KiB
37Time limit exceeded3.065s89896 KiB
38Runtime error115ms83968 KiB
39Runtime error112ms83384 KiB