#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
#define REP(i, n) for(int i = 0;i < n;i ++)
#define REP1(i, n) for(int i = 1;i <= n;i ++)
#define FILL(i, n) memset(i, n, sizeof(i))
#define X first
#define Y second
#define pb push_back
#define SZ(_a) ((int)(_a).size())
#define ALL(_a) (_a).begin(), (_a).end()
#ifdef brian
#define IOS()
template<typename T>void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...t>void _do(T &&x, t &&...X){cerr<<x<<", ";_do(X...);}
#define debug(...) {\
fprintf(stderr, "%s - %d (%s) = ", __PRETTY_FUNCTION__, __LINE__, #__VA_ARGS__);\
_do(__VA_ARGS__);\
}
#else
#define debug(...)
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#endif
const ll MAXn = 5e4 + 5;
const ll INF = ll(1e17);
#define R 0
#define C 1
ll r[MAXn], c[MAXn];
ll h, w, q;
set<ll> str, stc;
struct tg{
ll x, tp, i;
};
queue<tg> que;
void init(){
vector<tg> v;
REP1(i, h)v.pb({r[i], R, i});
REP1(i, w)v.pb({c[i], C, i});
sort(ALL(v), [](tg &a, tg &b){return a.x < b.x;});
while(SZ(que))que.pop();
for(auto &p:v)que.push(p);
str.clear(), stc.clear();
REP1(i, h)str.insert(i);
REP1(i, w)stc.insert(i);
}
ll mx = 0;
void gor(ll, ll, ll);
void goc(ll, ll, ll);
void gor(ll x,ll y, ll dis)// go along row x, changing y
{
debug(x, y, dis);
while(SZ(que) && que.front().x <= r[x])
{
auto t = que.front();que.pop();
if(t.tp == R)str.erase(t.i);
else stc.erase(t.i);
}
auto pit = stc.lower_bound(y);
auto nit = pit;
if(c[y] > r[x])nit ++;
if(nit != stc.end())debug(*nit);
if(pit != stc.begin())debug(*prev(pit));
mx = max({mx, y - 1 + dis, w - y + dis});
if(pit == stc.begin() && nit == stc.end())return;
else if(nit == stc.end())goc(x, *prev(pit), dis + y - (*prev(pit)));
else if(pit == stc.begin())goc(x, *nit, dis + (*nit) - y);
else
{
ll a = *prev(pit);
ll b = *nit;
if(c[a] < c[b])goc(x, a, dis + y - a);
else goc(x, b, dis + b - y);
}
}
void goc(ll x,ll y, ll dis)// go along column y, changing x
{
debug(x, y, dis);
while(SZ(que) && que.front().x <= c[y])
{
auto t = que.front();que.pop();
if(t.tp == R)str.erase(t.i);
else stc.erase(t.i);
}
auto pit = str.lower_bound(x);
auto nit = pit;
if(r[x] > c[y])nit ++;
mx = max({mx, x - 1 + dis, h - x + dis});
if(pit == str.begin() && nit == str.end())return;
else if(nit == str.end())gor(*prev(pit), y, dis + x - (*prev(pit)));
else if(pit == str.begin())gor(*nit, y, dis + (*nit) - x);
else
{
ll a = *prev(pit);
ll b = *nit;
if(c[a] < c[b])gor(a, y, dis + x - a);
else gor(b, y, dis + b - x);
}
}
int main(){
IOS();
cin>>h>>w>>q;
REP1(i, h)cin>>r[i];
REP1(i, w)cin>>c[i];
while(q--)
{
ll x, y;
cin>>x>>y;
debug(x, y);
mx = 0;
init();
gor(x, y, 0);
debug(mx);
init();
goc(x, y, 0);
cout<<mx<<endl;
}
}
| # |
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 |
293 ms |
860 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 |
- |
