This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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];
int ans;
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) ans = max(j-1, m-j);
else if (l == 0) ans = (r-j + solve(i, r, 1));
else if (r == m+1) ans = (j-l + solve(i, l, 1));
else ans = 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) ans = max(i-1, n-i);
else if (l == 0) ans = (r-i + solve(r, j, 0));
else if (r == n+1) ans = (i-l + solve(l, j, 0));
else ans = max(r-i + solve(r, j, 0), i-l + solve(l, j, 0));
}
return dp[i][q][j] = ans;
}
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 (stderr)
abduction2.cpp: In function 'int main()':
abduction2.cpp:105:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
105 | scanf("%d %d %d", &n, &m, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
abduction2.cpp:108:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
108 | scanf("%d", &a[0][i]);
| ~~~~~^~~~~~~~~~~~~~~~
abduction2.cpp:111:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
111 | scanf("%d", &a[1][i]);
| ~~~~~^~~~~~~~~~~~~~~~
abduction2.cpp:118:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
118 | scanf("%d %d", &i, &j);
| ~~~~~^~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |