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