#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <deque>
#include <map>
#include <set>
#include <complex>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <chrono>
#define ft first
#define sc second
#define pb push_back
#define len(v) (int)v.size()
// #define int ll
using namespace std;
typedef long long ll;
typedef long double ld;
vector<int> logt;
void built_logt(int n) {
logt = vector<int> (n + 2, 0);
int cnt = 0, now = 1;
for (int i = 0; i <= n + 1; i++) {
if(now * 2 == i) {
now *= 2;
cnt++;
}
logt[i] = cnt;
}
return;
}
struct sparse {
vector<vector<int>> table;
int n, log;
sparse() {}
sparse(vector<int>& have) {
n = len(have);
log = 1;
while((1 << log) <= n)
log *= 2;
table = vector<vector<int>> (log + 1, vector<int> (n + 1, 0));
for (int i = 0; i < n; i++) {
table[0][i] = have[i];
}
for (int logn = 1; logn < log; logn++) {
for (int i = 0; i < n; i++) {
int nxt = min(n - 1, (1 << (logn - 1)) + i);
table[logn][i] = max(table[logn - 1][i], table[logn - 1][nxt]);
}
}
return;
}
int get(int l, int r) {
int lenn = (r - l + 1);
int logn = logt[lenn];
int pred = (r - (1 << logn) + 1);
int ans = max(table[logn][l], table[logn][pred]);
return ans;
}
};
map<pair<int, int>, int> dp;
int w, h;
vector<int> a;
vector<int> b;
sparse as;
sparse bs;
int solve(int i, int j) {
// cout << i << " " << j << endl;
// cout << a[i] << " " << b[j] << endl;
if(dp.count({i, j}))
return dp[{i, j}];
if(a[i] > b[j]) {
int l = i, r = w;
while(r - l > 1) {
int now = (l + r) / 2;
if(bs.get(j, now) > a[i])
r = now;
else
l = now;
}
if(r == w)
dp[{i, j}] = max(dp[{i, j}], w - j);
else
dp[{i, j}] = max(dp[{i, j}], r - j + solve(i, r));
l = -1, r = i;
while(r - l > 1) {
int now = (l + r) / 2;
if(bs.get(now, j) > a[i])
l = now;
else
r = now;
}
for (int now = j; now >= 0; now--) {
if(bs.get(now, j) > a[i]) {
l = now;
break;
}
}
if(l == -1)
dp[{i, j}] = max(dp[{i, j}], j + 1);
else
dp[{i, j}] = max(dp[{i, j}], j - l + solve(i, l));
}
else {
int r = h;
for (int now = i; now < h; now++) {
if(as.get(i, now) > b[j]) {
r = now;
break;
}
}
if(r == h)
dp[{i, j}] = max(dp[{i, j}], h - i);
else
dp[{i, j}] = max(dp[{i, j}], r - i + solve(r, j));
int l = -1;
for (int now = i; now >= 0; now--) {
if(as.get(now, i) > b[j]) {
l = now;
break;
}
}
if(l == -1)
dp[{i, j}] = max(dp[{i, j}], i + 1);
else
dp[{i, j}] = max(dp[{i, j}], i - l + solve(l, j));
}
return dp[{i, j}];
}
signed main() {
#ifdef PC
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int q;
cin >> h >> w >> q;
a = vector<int> (h);
b = vector<int> (w);
for (int i = 0; i < h; i++) {
cin >> a[i];
}
for (int j = 0; j < w; j++) {
cin >> b[j];
}
built_logt(w + h);
as = *new sparse(a);
bs = *new sparse(b);
for (int k = 0; k < q; k++) {
int i, j;
cin >> i >> j;
i--, j--;
int ans = 1;
for (int j1 = j + 1; j1 < w; j1++) {
ans = max(ans, j1 - j + 1);
if(b[j1] > a[i]) {
ans = max(ans, j1 - j + solve(i, j1));
break;
}
}
for (int j1 = j - 1; j1 >= 0; j1--) {
ans = max(ans, j - j1 + 1);
if(b[j1] > a[i]) {
ans = max(ans, j - j1 + solve(i, j1));
break;
}
}
for (int i1 = i + 1; i1 < h; i1++) {
ans = max(ans, i1 - i + 1);
if(a[i1] > b[j]) {
ans = max(ans, i1 - i + solve(i1, j));
break;
}
}
for (int i1 = i - 1; i1 >= 0; i1--) {
ans = max(ans, i - i1 + 1);
if(a[i1] > b[j]) {
ans = max(ans, i - i1 + solve(i1, j));
break;
}
}
cout << ans - 1 << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
1656 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
