#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
int h, w, q, vh[50002], vw[50002];
int aint[200002], aint2[200002];
void build(int nod, int st, int dr)
{
if(st == dr)
{
aint[nod] = vh[st];
return;
}
int mid = (st + dr) / 2;
build(nod << 1, st, mid);
build(nod << 1|1, mid+1, dr);
aint[nod] = max(aint[nod << 1], aint[nod << 1|1]);
}
void build2(int nod, int st, int dr)
{
if(st == dr)
{
aint2[nod] = vw[st];
return;
}
int mid = (st + dr) / 2;
build2(nod << 1, st, mid);
build2(nod << 1|1, mid+1, dr);
aint2[nod] = max(aint2[nod << 1], aint2[nod << 1|1]);
}
int val;
int query(int nod, int st, int dr, int L, int R)
{
if(L > R)
return -1;
if(dr < L || st > R)
return -1;
if(aint[nod] <= val)
return -1;
if(st == dr)
return st;
int mid = (st + dr) / 2;
int ans = query(nod << 1|1, mid+1, dr, L, R);
if(ans != -1)
return ans;
return query(nod << 1, st, mid, L, R);
}
int query2(int nod, int st, int dr, int L, int R)
{
if(L > R)
return -1;
if(dr < L || st > R)
return -1;
if(aint[nod] <= val)
return -1;
if(st == dr)
return st;
int mid = (st + dr) / 2;
int ans = query2(nod << 1, st, mid, L, R);
if(ans != -1)
return ans;
return query2(nod << 1|1, mid+1, dr, L, R);
}
int queryw(int nod, int st, int dr, int L, int R)
{
if(L > R)
return -1;
if(dr < L || st > R)
return -1;
if(aint2[nod] <= val)
return -1;
if(st == dr)
return st;
int mid = (st + dr) / 2;
int ans = queryw(nod << 1|1, mid+1, dr, L, R);
if(ans != -1)
return ans;
return queryw(nod << 1, st, mid, L, R);
}
int queryw2(int nod, int st, int dr, int L, int R)
{
if(L > R)
return -1;
if(dr < L || st > R)
return -1;
if(aint2[nod] <= val)
return -1;
if(st == dr)
return st;
int mid = (st + dr) / 2;
int ans = queryw2(nod << 1, st, mid, L, R);
if(ans != -1)
return ans;
return queryw2(nod << 1|1, mid+1, dr, L, R);
}
map<pair<pair<int, int>, int>, int>bst;
int solve(int L, int C)
{
bst.clear();
deque<pair<pair<int, int>, pair<int, int> > >d;
d.pb({{L, C}, {0, 1}});
d.pb({{L, C}, {0, 2}});
int ia, ib, ic, id;
int ans = 0;
while(!d.empty())
{
pair<pair<int, int>, pair<int, int> > nod = d[0];
d.pop_front();
L = nod.fi.fi;
C = nod.fi.se;
ans = max(ans, nod.se.fi);
if(nod.se.se == 1)
{
val = vh[L];
ic = queryw2(1, 1, w, C+1, w);
id = queryw(1, 1, w, 1, C-1);
if(ic != -1)
{
if(bst.find({{L, ic}, 2}) != bst.end())
{
if(nod.se.fi + ic - C <= bst[{{L, ic}, 2}])
continue;
bst[{{L, ic}, 2}] = nod.se.fi + ic - C;
d.pb({{L, ic}, {nod.se.fi + ic - C, 2}});
}
else
{
bst[{{L, ic}, 2}] = nod.se.fi + ic - C;
d.pb({{L, ic}, {nod.se.fi + ic - C, 2}});
}
}
else
ans = max(ans, nod.se.fi + w - C);
if(id != -1)
{
if(bst.find({{L, id}, 2}) != bst.end())
{
if(nod.se.fi + C - id <= bst[{{L, ic}, 2}])
continue;
bst[{{L, id}, 2}] = nod.se.fi + C - id;
d.pb({{L, id}, {nod.se.fi + C - id, 2}});
}
else
{
bst[{{L, id}, 2}] = nod.se.fi + C - id;
d.pb({{L, id}, {nod.se.fi + C - id, 2}});
}
}
else
ans = max(ans, nod.se.fi + C - 1);
}
else
{
val = vw[C];
ia = query2(1, 1, h, L+1, h);
ib = query(1, 1, h, 1, L-1);
if(ia != -1)
{
if(bst.find({{ia, C}, 1}) != bst.end())
{
if(nod.se.fi + ia - L <= bst[{{ia, C}, 1}])
continue;
bst[{{ia, C}, 1}] = nod.se.fi + ia - L;
d.pb({{ia, C}, {nod.se.fi + ia - L, 1}});
}
else
{
bst[{{ia, C}, 1}] = nod.se.fi + ia - L;
d.pb({{ia, C}, {nod.se.fi + ia - L, 1}});
}
}
else
ans = max(ans, nod.se.fi + h - L);
if(ib != -1)
{
if(bst.find({{ib, C}, 1}) != bst.end())
{
if(nod.se.fi + L - ib <= bst[{{ib, C}, 1}])
continue;
bst[{{ib, C}, 1}] = nod.se.fi + L - ib;
d.pb({{ib, C}, {nod.se.fi + L - ib, 1}});
}
else
{
bst[{{ib, C}, 1}] = nod.se.fi + L - ib;
d.pb({{ib, C}, {nod.se.fi + L - ib, 1}});
}
}
else
ans = max(ans, nod.se.fi + L - 1);
}
}
return ans;
}
int main()
{
cin >> h >> w >> q;
for(int i = 1; i <= h; ++i)
cin >> vh[i];
for(int i = 1; i <= w; ++i)
cin >> vw[i];
build(1, 1, h);
build2(1, 1, w);
for(int i = 1; i <= q; ++i)
{
int L, C;
cin >> L >> C;
cout << solve(L, C) << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
