#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e4+10;
const int maxl = 17;
int n, m;
int a[2][maxn];
map<int, int> dp[maxn][2];
struct SparseTable
{
int tab[2][2][maxn][maxl];
void build(void)
{
for (int i = 1; i <= n; i++)
{
if (i > 1) tab[0][0][i][0] = a[0][i-1];
if (i < n) tab[0][1][i][0] = a[0][i+1];
}
for (int i = 1; i <= m; i++)
{
if (i > 1) tab[1][0][i][0] = a[1][i-1];
if (i < m) tab[1][1][i][0] = a[1][i+1];
}
for (int j = 1; j < maxl; j++)
{
for (int i = 1; i <= n; i++)
{
if (i-(1<<j) > 0)
tab[0][0][i][j] = max(tab[0][0][i][j-1], tab[0][0][i-(1<<(j-1))][j-1]);
if (i+(1<<j) <= n)
tab[0][1][i][j] = max(tab[0][1][i][j-1], tab[0][1][i+(1<<(j-1))][j-1]);
}
for (int i = 1; i <= m; i++)
{
if (i-(1<<j) > 0)
tab[1][0][i][j] = max(tab[1][0][i][j-1], tab[1][0][i-(1<<(j-1))][j-1]);
if (i+(1<<j) <= m)
tab[1][1][i][j] = max(tab[1][1][i][j-1], tab[1][1][i+(1<<(j-1))][j-1]);
}
}
}
int get_l(int pos, int x, int q)
{
for (int i = maxl-1; i >= 0; i--)
if (pos-(1<<i) > 0 && tab[q][0][pos][i] < x)
pos -= (1<<i);
return pos-1;
}
int get_r(int pos, int x, int q)
{
for (int i = maxl-1; i >= 0; i--)
if (pos+(1<<i) <= (!q ? n : m) && tab[q][1][pos][i] < x)
pos += (1<<i);
return pos+1;
}
} ST;
int solve(int i, int j, int q)
{
if (dp[i][q].find(j) != dp[i][q].end()) return dp[i][q][j];
if (!q)
{
int l = ST.get_l(j, a[0][i], 1), r = ST.get_r(j, a[0][i], 1);
if (l == 0 && r == m+1) return max(j-1, m-j);
if (l == 0) return (r-j + solve(i, r, 1));
if (r == m+1) return (j-l + solve(i, l, 1));
return max(r-j + solve(i, r, 1), j-l + solve(i, l, 1));
}
else
{
int l = ST.get_l(i, a[1][j], 0), r = ST.get_r(i, a[1][j], 0);
if (l == 0 && r == n+1) return max(i-1, n-i);
if (l == 0) return (r-i + solve(r, j, 0));
if (r == n+1) return (i-l + solve(l, j, 0));
return max(r-i + solve(r, j, 0), i-l + solve(l, j, 0));
}
}
int main(void)
{
int q;
scanf("%d %d %d", &n, &m, &q);
for (int i = 1; i <= n; i++)
scanf("%d", &a[0][i]);
for (int i = 1; i <= m; i++)
scanf("%d", &a[1][i]);
ST.build();
while (q--)
{
int i, j;
scanf("%d %d", &i, &j);
printf("%d\n", max(solve(i, j, 0), solve(i, j, 1)));
}
}
Compilation message
abduction2.cpp: In function 'int main()':
abduction2.cpp:103:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
103 | scanf("%d %d %d", &n, &m, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
abduction2.cpp:106:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
106 | scanf("%d", &a[0][i]);
| ~~~~~^~~~~~~~~~~~~~~~
abduction2.cpp:109:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
109 | scanf("%d", &a[1][i]);
| ~~~~~^~~~~~~~~~~~~~~~
abduction2.cpp:116:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
116 | scanf("%d %d", &i, &j);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 8 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 9 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 10 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 11 |
Correct |
3 ms |
4992 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 8 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 9 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 10 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 11 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 12 |
Correct |
4 ms |
5632 KB |
Output is correct |
| 13 |
Correct |
5 ms |
5632 KB |
Output is correct |
| 14 |
Correct |
5 ms |
5632 KB |
Output is correct |
| 15 |
Correct |
5 ms |
5632 KB |
Output is correct |
| 16 |
Correct |
5 ms |
5632 KB |
Output is correct |
| 17 |
Correct |
5 ms |
5632 KB |
Output is correct |
| 18 |
Correct |
5 ms |
5632 KB |
Output is correct |
| 19 |
Execution timed out |
5051 ms |
5632 KB |
Time limit exceeded |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 8 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 9 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 10 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 11 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 12 |
Correct |
4 ms |
5632 KB |
Output is correct |
| 13 |
Correct |
5 ms |
5632 KB |
Output is correct |
| 14 |
Correct |
5 ms |
5632 KB |
Output is correct |
| 15 |
Correct |
5 ms |
5632 KB |
Output is correct |
| 16 |
Correct |
5 ms |
5632 KB |
Output is correct |
| 17 |
Correct |
5 ms |
5632 KB |
Output is correct |
| 18 |
Correct |
5 ms |
5632 KB |
Output is correct |
| 19 |
Execution timed out |
5051 ms |
5632 KB |
Time limit exceeded |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
5632 KB |
Output is correct |
| 2 |
Correct |
21 ms |
5680 KB |
Output is correct |
| 3 |
Correct |
26 ms |
5632 KB |
Output is correct |
| 4 |
Correct |
28 ms |
5632 KB |
Output is correct |
| 5 |
Correct |
31 ms |
5632 KB |
Output is correct |
| 6 |
Correct |
32 ms |
5632 KB |
Output is correct |
| 7 |
Correct |
30 ms |
5632 KB |
Output is correct |
| 8 |
Execution timed out |
5007 ms |
5632 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 5 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 6 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 7 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 8 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 9 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 10 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 11 |
Correct |
3 ms |
4992 KB |
Output is correct |
| 12 |
Correct |
4 ms |
5632 KB |
Output is correct |
| 13 |
Correct |
5 ms |
5632 KB |
Output is correct |
| 14 |
Correct |
5 ms |
5632 KB |
Output is correct |
| 15 |
Correct |
5 ms |
5632 KB |
Output is correct |
| 16 |
Correct |
5 ms |
5632 KB |
Output is correct |
| 17 |
Correct |
5 ms |
5632 KB |
Output is correct |
| 18 |
Correct |
5 ms |
5632 KB |
Output is correct |
| 19 |
Execution timed out |
5051 ms |
5632 KB |
Time limit exceeded |
| 20 |
Halted |
0 ms |
0 KB |
- |
