5368 2023. 04. 26 16:40:02 zsombor Hegyi levegő cpp17 Időlimit túllépés 0/100 3.104s 115388 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";
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Időlimit túllépés 3.058s 32424 KiB
2 Időlimit túllépés 3.078s 32684 KiB
subtask2 0/19
3 Futási hiba 29ms 65392 KiB
4 Futási hiba 25ms 65576 KiB
5 Időlimit túllépés 3.062s 33380 KiB
6 Időlimit túllépés 3.075s 33520 KiB
7 Időlimit túllépés 3.076s 34076 KiB
8 Időlimit túllépés 3.082s 34120 KiB
9 Időlimit túllépés 3.062s 34300 KiB
10 Időlimit túllépés 3.081s 34880 KiB
subtask3 0/20
11 Időlimit túllépés 3.046s 34656 KiB
12 Futási hiba 25ms 66928 KiB
13 Időlimit túllépés 3.069s 35728 KiB
14 Időlimit túllépés 3.072s 45584 KiB
15 Időlimit túllépés 3.069s 61336 KiB
subtask4 0/20
16 Időlimit túllépés 3.059s 61332 KiB
17 Időlimit túllépés 3.039s 86752 KiB
18 Időlimit túllépés 3.065s 61528 KiB
19 Időlimit túllépés 3.062s 61632 KiB
20 Időlimit túllépés 3.082s 61628 KiB
subtask5 0/31
21 Időlimit túllépés 3.052s 60428 KiB
22 Időlimit túllépés 3.053s 55512 KiB
23 Időlimit túllépés 3.104s 55280 KiB
24 Időlimit túllépés 3.062s 55336 KiB
25 Időlimit túllépés 3.072s 55444 KiB
26 Időlimit túllépés 3.055s 55268 KiB
27 Időlimit túllépés 3.078s 55416 KiB
28 Futási hiba 39ms 71148 KiB
29 Futási hiba 35ms 70900 KiB
subtask6 0/10
30 Időlimit túllépés 3.068s 115388 KiB
31 Időlimit túllépés 3.088s 90076 KiB
32 Időlimit túllépés 3.063s 90084 KiB
33 Időlimit túllépés 3.068s 90128 KiB
34 Időlimit túllépés 3.078s 90108 KiB
35 Időlimit túllépés 3.075s 90052 KiB
36 Időlimit túllépés 3.072s 89876 KiB
37 Időlimit túllépés 3.065s 89896 KiB
38 Futási hiba 115ms 83968 KiB
39 Futási hiba 112ms 83384 KiB