#include <map>
#include <tuple>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int tree_a[131072], tree_b[131072];
vector<tuple<int, int, int>> tv;
void interval_front(int i, int b, int e, int l, int r) {
if (r < b || e < l) return;
if (l <= b && e <= r) {
tv.push_back({ i, b, e });
return;
}
int m = (b + e) / 2;
interval_front(i * 2 + 1, b, m, l, r);
interval_front(i * 2 + 2, m + 1, e, l, r);
}
void interval_back(int i, int b, int e, int l, int r) {
if (r < b || e < l) return;
if (l <= b && e <= r) {
tv.push_back({ i, b, e });
return;
}
int m = (b + e) / 2;
interval_back(i * 2 + 2, m + 1, e, l, r);
interval_back(i * 2 + 1, b, m, l, r);
}
int lower_bound_left_real_a(int i, int b, int e, int v) {
if (b == e) return b;
int m = (b + e) / 2;
if (tree_a[i * 2 + 2] > v) return lower_bound_left_real_a(i * 2 + 2, m + 1, e, v);
return lower_bound_left_real_a(i * 2 + 1, b, m, v);
}
int lower_bound_left_real_b(int i, int b, int e, int v) {
if (b == e) return b;
int m = (b + e) / 2;
if (tree_b[i * 2 + 2] > v) return lower_bound_left_real_b(i * 2 + 2, m + 1, e, v);
return lower_bound_left_real_b(i * 2 + 1, b, m, v);
}
int lower_bound_right_real_a(int i, int b, int e, int v) {
if (b == e) return b;
int m = (b + e) / 2;
if (tree_a[i * 2 + 1] > v) return lower_bound_right_real_a(i * 2 + 1, b, m, v);
return lower_bound_right_real_a(i * 2 + 2, m + 1, e, v);
}
int lower_bound_right_real_b(int i, int b, int e, int v) {
if (b == e) return b;
int m = (b + e) / 2;
if (tree_b[i * 2 + 1] > v) return lower_bound_right_real_b(i * 2 + 1, b, m, v);
return lower_bound_right_real_b(i * 2 + 2, m + 1, e, v);
}
int lower_bound_left_a(int x, int v) {
tv.clear();
interval_back(0, 0, 65535, 0, x);
for (auto &i: tv) {
auto [ a, b, c ] = i;
if (tree_a[a] > v) return lower_bound_left_real_a(a, b, c, v);
}
return -1;
}
int lower_bound_left_b(int x, int v) {
tv.clear();
interval_back(0, 0, 65535, 0, x);
for (auto &i: tv) {
auto [ a, b, c ] = i;
if (tree_b[a] > v) return lower_bound_left_real_b(a, b, c, v);
}
return -1;
}
int lower_bound_right_a(int x, int v) {
tv.clear();
interval_front(0, 0, 65535, x, 65535);
for (auto &i: tv) {
auto [ a, b, c ] = i;
if (tree_a[a] > v) return lower_bound_right_real_a(a, b, c, v);
}
return 65536;
}
int lower_bound_right_b(int x, int v) {
tv.clear();
interval_front(0, 0, 65535, x, 65535);
for (auto &i: tv) {
auto [ a, b, c ] = i;
if (tree_b[a] > v) return lower_bound_right_real_b(a, b, c, v);
}
return 65536;
}
int h, w, q;
int a[50006], b[50006], rt[100006];
pair<int, bool> lt[100006];
vector<pair<int, long long>> v[100006];
vector<int> compress;
int main() {
scanf("%d%d%d", &w, &h, &q);
for (int i = 0; i < w; i++) scanf("%d", a + i);
for (int i = 0; i < h; i++) scanf("%d", b + i);
for (int i = 0; i < w; i++) compress.push_back(a[i]);
for (int i = 0; i < h; i++) compress.push_back(b[i]);
sort(compress.begin(), compress.end());
for (int i = 0; i < w; i++) a[i] = lower_bound(compress.begin(), compress.end(), a[i]) - compress.begin();
for (int i = 0; i < h; i++) b[i] = lower_bound(compress.begin(), compress.end(), b[i]) - compress.begin();
for (int i = 0; i < w; i++) lt[a[i]] = { i, false };
for (int i = 0; i < h; i++) lt[b[i]] = { i, true };
for (int i = 0; i < w; i++) tree_a[65535 + i] = a[i];
for (int i = 0; i < h; i++) tree_b[65535 + i] = b[i];
for (int i = 65534; i >= 0; i--) {
tree_a[i] = max(tree_a[i * 2 + 1], tree_a[i * 2 + 2]);
tree_b[i] = max(tree_b[i * 2 + 1], tree_b[i * 2 + 2]);
}
for (int i = 0; i < q; i++) {
int s, t;
scanf("%d%d", &t, &s);
s--, t--;
long long res = 0;
if (s > 0) { // up
for (int j = 0; j < h + w; j++) v[j].clear(), rt[j] = -1;
int it = lower_bound_left_b(s - 1, a[t]);
if (it < 0) res = max(res, (long long)s);
else {
v[b[it]].push_back({ t, s - it });
rt[b[it]] = lower_bound_left_a(t, it);
for (int i = 0; i < h + w; i++) if (!v[i].empty()) {
if (!lt[i].second) {
int above = rt[i], bottom = lower_bound_right_b(v[i].front().first, a[lt[i].first]);
if (above < 0) for (auto &j: v[i]) res = max(res, j.second + j.first);
else {
int tmp = lower_bound_left_a(lt[i].first, b[above]);
if (!v[b[above]].empty() && rt[b[above]] != tmp) v[b[above]].clear();
long long ret = 0;
for (auto &j: v[i]) ret = max(ret, j.second + (j.first - above));
v[b[above]].push_back({ lt[i].first, ret });
rt[b[above]] = tmp;
}
if (bottom >= 65536) for (auto &j: v[i]) res = max(res, j.second + (h - 1 - j.first));
else {
int tmp = lower_bound_left_a(lt[i].first, b[bottom]);
if (!v[b[bottom]].empty() && rt[b[bottom]] != tmp) v[b[bottom]].clear();
long long ret = 0;
for (auto &j: v[i]) ret = max(ret, j.second + (bottom - j.first));
v[b[bottom]].push_back({ lt[i].first, ret });
rt[b[bottom]] = tmp;
}
} else {
int left = rt[i], right = lower_bound_right_a(v[i].front().first, b[lt[i].first]);
if (left < 0) for (auto &j: v[i]) res = max(res, j.second + j.first);
else {
int tmp = lower_bound_left_b(lt[i].first, a[left]);
if (!v[a[left]].empty() && rt[a[left]] != tmp) v[a[left]].clear();
long long ret = 0;
for (auto &j: v[i]) ret = max(ret, j.second + (j.first - left));
v[a[left]].push_back({ lt[i].first, ret });
rt[a[left]] = tmp;
}
if (right >= 65536) for (auto &j: v[i]) res = max(res, j.second + (w - 1 - j.first));
else {
int tmp = lower_bound_left_b(lt[i].first, a[right]);
if (!v[a[right]].empty() && rt[a[right]] != tmp) v[a[right]].clear();
long long ret = 0;
for (auto &j: v[i]) ret = max(ret, j.second + (right - j.first));
v[a[right]].push_back({ lt[i].first, ret });
rt[a[right]] = tmp;
}
}
}
}
}
if (s < h - 1) { // down
for (int j = 0; j < h + w; j++) v[j].clear(), rt[j] = -1;
int it = lower_bound_right_b(s + 1, a[t]);
if (it >= 65536) res = max(res, (long long)(h - 1 - s));
else {
v[b[it]].push_back({ t, it - s });
rt[b[it]] = lower_bound_left_a(t, it);
for (int i = 0; i < h + w; i++) if (!v[i].empty()) {
if (!lt[i].second) {
int above = rt[i], bottom = lower_bound_right_b(v[i].front().first, a[lt[i].first]);
if (above < 0) for (auto &j: v[i]) res = max(res, j.second + j.first);
else {
int tmp = lower_bound_left_a(lt[i].first, b[above]);
if (!v[b[above]].empty() && rt[b[above]] != tmp) v[b[above]].clear();
long long ret = 0;
for (auto &j: v[i]) ret = max(ret, j.second + (j.first - above));
v[b[above]].push_back({ lt[i].first, ret });
rt[b[above]] = tmp;
}
if (bottom >= 65536) for (auto &j: v[i]) res = max(res, j.second + (h - 1 - j.first));
else {
int tmp = lower_bound_left_a(lt[i].first, b[bottom]);
if (!v[b[bottom]].empty() && rt[b[bottom]] != tmp) v[b[bottom]].clear();
long long ret = 0;
for (auto &j: v[i]) ret = max(ret, j.second + (bottom - j.first));
v[b[bottom]].push_back({ lt[i].first, ret });
rt[b[bottom]] = tmp;
}
} else {
int left = rt[i], right = lower_bound_right_a(v[i].front().first, b[lt[i].first]);
if (left < 0) for (auto &j: v[i]) res = max(res, j.second + j.first);
else {
int tmp = lower_bound_left_b(lt[i].first, a[left]);
if (!v[a[left]].empty() && rt[a[left]] != tmp) v[a[left]].clear();
long long ret = 0;
for (auto &j: v[i]) ret = max(ret, j.second + (j.first - left));
v[a[left]].push_back({ lt[i].first, ret });
rt[a[left]] = tmp;
}
if (right >= 65536) for (auto &j: v[i]) res = max(res, j.second + (w - 1 - j.first));
else {
int tmp = lower_bound_left_b(lt[i].first, a[right]);
if (!v[a[right]].empty() && rt[a[right]] != tmp) v[a[right]].clear();
long long ret = 0;
for (auto &j: v[i]) ret = max(ret, j.second + (right - j.first));
v[a[right]].push_back({ lt[i].first, ret });
rt[a[right]] = tmp;
}
}
}
}
}
if (t > 0) { // left
for (int j = 0; j < h + w; j++) v[j].clear(), rt[j] = -1;
int it = lower_bound_left_a(t - 1, b[s]);
if (it < 0) res = max(res, (long long)t);
else {
v[a[it]].push_back({ s, t - it });
rt[a[it]] = lower_bound_left_b(s, it);
for (int i = 0; i < h + w; i++) if (!v[i].empty()) {
if (!lt[i].second) {
int above = rt[i], bottom = lower_bound_right_b(v[i].front().first, a[lt[i].first]);
if (above < 0) for (auto &j: v[i]) res = max(res, j.second + j.first);
else {
int tmp = lower_bound_left_a(lt[i].first, b[above]);
if (!v[b[above]].empty() && rt[b[above]] != tmp) v[b[above]].clear();
long long ret = 0;
for (auto &j: v[i]) ret = max(ret, j.second + (j.first - above));
v[b[above]].push_back({ lt[i].first, ret });
rt[b[above]] = tmp;
}
if (bottom >= 65536) for (auto &j: v[i]) res = max(res, j.second + (h - 1 - j.first));
else {
int tmp = lower_bound_left_a(lt[i].first, b[bottom]);
if (!v[b[bottom]].empty() && rt[b[bottom]] != tmp) v[b[bottom]].clear();
long long ret = 0;
for (auto &j: v[i]) ret = max(ret, j.second + (bottom - j.first));
v[b[bottom]].push_back({ lt[i].first, ret });
rt[b[bottom]] = tmp;
}
} else {
int left = rt[i], right = lower_bound_right_a(v[i].front().first, b[lt[i].first]);
if (left < 0) for (auto &j: v[i]) res = max(res, j.second + j.first);
else {
int tmp = lower_bound_left_b(lt[i].first, a[left]);
if (!v[a[left]].empty() && rt[a[left]] != tmp) v[a[left]].clear();
long long ret = 0;
for (auto &j: v[i]) ret = max(ret, j.second + (j.first - left));
v[a[left]].push_back({ lt[i].first, ret });
rt[a[left]] = tmp;
}
if (right >= 65536) for (auto &j: v[i]) res = max(res, j.second + (w - 1 - j.first));
else {
int tmp = lower_bound_left_b(lt[i].first, a[right]);
if (!v[a[right]].empty() && rt[a[right]] != tmp) v[a[right]].clear();
long long ret = 0;
for (auto &j: v[i]) ret = max(ret, j.second + (right - j.first));
v[a[right]].push_back({ lt[i].first, ret });
rt[a[right]] = tmp;
}
}
}
}
}
if (t < w - 1) { // right
for (int j = 0; j < h + w; j++) v[j].clear(), rt[j] = -1;
int it = lower_bound_right_a(t + 1, b[s]);
if (it >= 65536) res = max(res, (long long)(w - 1 - t));
else {
v[a[it]].push_back({ s, it - t });
rt[a[it]] = lower_bound_left_b(s, it);
for (int i = 0; i < h + w; i++) if (!v[i].empty()) {
if (!lt[i].second) {
int above = rt[i], bottom = lower_bound_right_b(v[i].front().first, a[lt[i].first]);
if (above < 0) for (auto &j: v[i]) res = max(res, j.second + j.first);
else {
int tmp = lower_bound_left_a(lt[i].first, b[above]);
if (!v[b[above]].empty() && rt[b[above]] != tmp) v[b[above]].clear();
long long ret = 0;
for (auto &j: v[i]) ret = max(ret, j.second + (j.first - above));
v[b[above]].push_back({ lt[i].first, ret });
rt[b[above]] = tmp;
}
if (bottom >= 65536) for (auto &j: v[i]) res = max(res, j.second + (h - 1 - j.first));
else {
int tmp = lower_bound_left_a(lt[i].first, b[bottom]);
if (!v[b[bottom]].empty() && rt[b[bottom]] != tmp) v[b[bottom]].clear();
long long ret = 0;
for (auto &j: v[i]) ret = max(ret, j.second + (bottom - j.first));
v[b[bottom]].push_back({ lt[i].first, ret });
rt[b[bottom]] = tmp;
}
} else {
int left = rt[i], right = lower_bound_right_a(v[i].front().first, b[lt[i].first]);
if (left < 0) for (auto &j: v[i]) res = max(res, j.second + j.first);
else {
int tmp = lower_bound_left_b(lt[i].first, a[left]);
if (!v[a[left]].empty() && rt[a[left]] != tmp) v[a[left]].clear();
long long ret = 0;
for (auto &j: v[i]) ret = max(ret, j.second + (j.first - left));
v[a[left]].push_back({ lt[i].first, ret });
rt[a[left]] = tmp;
}
if (right >= 65536) for (auto &j: v[i]) res = max(res, j.second + (w - 1 - j.first));
else {
int tmp = lower_bound_left_b(lt[i].first, a[right]);
if (!v[a[right]].empty() && rt[a[right]] != tmp) v[a[right]].clear();
long long ret = 0;
for (auto &j: v[i]) ret = max(ret, j.second + (right - j.first));
v[a[right]].push_back({ lt[i].first, ret });
rt[a[right]] = tmp;
}
}
}
}
}
printf("%lld\n", res);
}
}
Compilation message
abduction2.cpp: In function 'int lower_bound_left_a(int, int)':
abduction2.cpp:65:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
65 | auto [ a, b, c ] = i;
| ^
abduction2.cpp: In function 'int lower_bound_left_b(int, int)':
abduction2.cpp:75:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
75 | auto [ a, b, c ] = i;
| ^
abduction2.cpp: In function 'int lower_bound_right_a(int, int)':
abduction2.cpp:85:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
85 | auto [ a, b, c ] = i;
| ^
abduction2.cpp: In function 'int lower_bound_right_b(int, int)':
abduction2.cpp:95:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
95 | auto [ a, b, c ] = i;
| ^
abduction2.cpp: In function 'int main()':
abduction2.cpp:108:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
108 | scanf("%d%d%d", &w, &h, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
abduction2.cpp:109:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
109 | for (int i = 0; i < w; i++) scanf("%d", a + i);
| ~~~~~^~~~~~~~~~~~~
abduction2.cpp:110:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
110 | for (int i = 0; i < h; i++) scanf("%d", b + i);
| ~~~~~^~~~~~~~~~~~~
abduction2.cpp:126:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
126 | scanf("%d%d", &t, &s);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3152 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3148 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 4 |
Correct |
2 ms |
3156 KB |
Output is correct |
| 5 |
Correct |
2 ms |
3160 KB |
Output is correct |
| 6 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 7 |
Incorrect |
3 ms |
3156 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3152 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3148 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 4 |
Correct |
2 ms |
3156 KB |
Output is correct |
| 5 |
Correct |
2 ms |
3160 KB |
Output is correct |
| 6 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 7 |
Incorrect |
3 ms |
3156 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3152 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3148 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 4 |
Correct |
2 ms |
3156 KB |
Output is correct |
| 5 |
Correct |
2 ms |
3160 KB |
Output is correct |
| 6 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 7 |
Incorrect |
3 ms |
3156 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
3276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3152 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3148 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 4 |
Correct |
2 ms |
3156 KB |
Output is correct |
| 5 |
Correct |
2 ms |
3160 KB |
Output is correct |
| 6 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 7 |
Incorrect |
3 ms |
3156 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
