#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
const int N = 50007;
int a[2][N];
int l[2][N], r[2][N];
signed main() {
#ifdef HOME
freopen("input.txt", "r", stdin);
#else
#define endl '\n'
ios_base::sync_with_stdio(0); cin.tie(0);
#endif
int n, m, q;
cin >> n >> m >> q;
for (int i = 0; i < n; ++i) {
cin >> a[0][i];
}
for (int i = 0; i < m; ++i) {
cin >> a[1][i];
}
struct Line {
int t;
int i, x;
};
auto comp = [&](Line a, Line b) {
return a.x > b.x;
};
vector <Line> s;
for (int i = 0; i < n; ++i) {
s.app({0, i, a[0][i]});
}
for (int i = 0; i < m; ++i) {
s.app({1, i, a[1][i]});
}
sort(all(s), comp);
while (q--) {
int x, y;
cin >> x >> y;
--x; --y;
vector <int> bor[2];
bor[0] = {-1, m};
bor[1] = {-1, n};
for (int t = 0; t < 2; ++t) {
for (int i = 0; i < bor[t].back(); ++i) {
l[t][i] = i - bor[t][0];
r[t][i] = bor[t].back() - i;
}
}
//slx - start go left on horizontal line
int slx = -1;
for (int i = y - 1; i >= 0; --i) {
if (a[1][i] > a[0][x]) {
slx = i;
break;
}
}
int srx = m;
for (int i = y + 1; i < m; ++i) {
if (a[1][i] > a[0][x]) {
srx = i;
break;
}
}
int sly = -1;
for (int i = x - 1; i >= 0; --i) {
if (a[0][i] > a[1][y]) {
sly = i;
break;
}
}
int sry = n;
for (int i = x + 1; i < n; ++i) {
if (a[0][i] > a[1][y]) {
sry = i;
break;
}
}
int ans = 0;
ans = max(ans, y - slx);
ans = max(ans, srx - y);
ans = max(ans, x - sly);
ans = max(ans, sry - x);
for (auto e : s) {
if (e.t == 0) {
cout << "row " << e.i << endl;
for (int i = 0; i < m; ++i)
cout << l[0][i] << ' ';
cout << endl;
for (int i = 0; i < m; ++i)
cout << r[0][i] << ' ';
cout << endl;
cout << endl;
}
else {
cout << "col " << e.i << endl;
for (int i = 0; i < n; ++i)
cout << l[1][i] << ' ';
cout << endl;
for (int i = 0; i < n; ++i)
cout << r[1][i] << ' ';
cout << endl;
cout << endl;
}
if (e.t == 0) {
if (e.i == sly) {
ans = max(ans, max(l[e.t][y], r[e.t][y]) + x - sly);
}
if (e.i == sry) {
ans = max(ans, max(l[e.t][y], r[e.t][y]) + sry - x);
}
}
else {
if (e.i == slx) {
ans = max(ans, max(l[e.t][x], r[e.t][x]) + y - slx);
}
if (e.i == srx) {
ans = max(ans, max(l[e.t][x], r[e.t][x]) + srx - y);
}
}
bor[e.t^1].app(e.i);
sort(all(bor[e.t^1]));
int pos = -1;
for (int i = 0; i < bor[e.t^1].size(); ++i) {
if (bor[e.t^1][i] == e.i) {
pos = i;
break;
}
}
int link_l = bor[e.t^1][pos - 1];
for (int i = link_l + 1; i <= e.i; ++i) {
cout << "upd " << i << endl;
if (i == 1) {
cout << "tak " << e.i - i << ' ' << max(l[e.t][i], r[e.t][i]) << endl;
}
r[e.t^1][i] = e.i - i + max(l[e.t][i], r[e.t][i]);
}
int link_r = bor[e.t^1][pos + 1];
for (int i = e.i; i < link_r; ++i) {
l[e.t^1][i] = i - e.i + max(l[e.t][i], r[e.t][i]);
}
if (e.t == 1) {
exit(0);
}
}
--ans;
cout << ans << endl;
}
}
Compilation message
abduction2.cpp: In function 'int main()':
abduction2.cpp:150:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < bor[e.t^1].size(); ++i) {
~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
