#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;
if(aint[nod << 1|1] > val && R > mid)
return query(nod << 1|1, mid+1, dr, L, R);
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;
if(aint[nod << 1] > val && mid >= L)
return query2(nod << 1, st, mid, L, R);
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;
if(aint2[nod << 1|1] > val && R > mid)
return queryw(nod << 1|1, mid+1, dr, L, R);
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;
if(aint2[nod << 1] > val && mid >= L)
return queryw2(nod << 1, st, mid, L, R);
return queryw2(nod << 1|1, mid+1, dr, L, R);
}
int solve(int L, int C)
{
deque<pair<pair<int, int>, pair<ll, int> > >d;
val = vw[C];
int ia = query2(1, 1, h, L+1, h);
int ib = query(1, 1, h, 1, L-1);
val = vh[L];
int ic = queryw2(1, 1, w, C+1, w);
int id = queryw(1, 1, w, 1, C-1);
ll ans = 0;
if(ia != -1)
d.pb({{ia, C}, {ia - L, 1}});
else
ans = max(ans, 0LL + h - L);
if(ib != -1)
d.pb({{ib, C}, {L - ib, 1}});
else
ans = max(ans, 0LL + L - 1);
if(ic != -1)
d.pb({{L, ic}, {ic - C, 2}});
else
ans = max(ans, 0LL + w - C);
if(id != -1)
d.pb({{L, id}, {C - id, 2}});
else
ans = max(ans, 0LL + C - 1);
while(!d.empty())
{
pair<pair<int, int>, pair<ll, 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)
d.pb({{L, ic}, {nod.se.fi + ic - C, 2}});
else
ans = max(ans, nod.se.fi + w - C);
if(id != -1)
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)
d.pb({{ia, C}, {nod.se.fi + ia - L, 1}});
else
ans = max(ans, nod.se.fi + h - L);
if(ib != -1)
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;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
7 ms |
552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
