#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define cerr if(0)cerr
using namespace std;
using pii = pair<int, int>;
const int MAXH = 5e4+1;
int h, w, a[MAXH], b[MAXH];
int max_a, max_b;
int q;
list<pii> rows, colns;
list<pii>::iterator operator+(const list<pii>::iterator& iter, const int& increment) {
auto res_iter = iter;
if(increment >= 0) {
for(int i=0; i<increment; ++i) {
++res_iter;
}
}
else {
for(int i=0; i<abs(increment); ++i) {
--res_iter;
}
}
return res_iter;
}
inline void init() {
rows.clear(), colns.clear();
rows.push_back(mp(1e9+1, -1));
for(int i=0; i<h; ++i) {
rows.push_back(mp(a[i], i));
}
colns.push_back(mp(1e9+1, -1));
for(int i=0; i<w; ++i) {
colns.push_back(mp(b[i], i));
}
}
bool lol=0;
list<pii>::iterator go_left(list<pii>& l, list<pii>::iterator x, int val) {
auto it = x;
--it;
while(true) {
if((*it).st < val) {
auto del = it;
it--;
l.erase(del);
}
else {
break;
}
}
return it;
}
list<pii>::iterator go_right(list<pii>& l, list<pii>::iterator x, int val) {
auto it = x;
++it;
while(it != l.end()) {
if((*it).st < val) {
it = l.erase(it);
}
else {
break;
}
}
if(it == l.end()) {
return l.begin();
}
return it;
}
int solve(list<pii>::iterator x, list<pii>::iterator y, bool turn) {
cerr<<"solve "<<(*x).nd<<' '<<(*y).nd<<' '<<turn<<" "<<(*x).st<<' '<<(*y).st<<'\n';
if(!turn) {
auto it = go_left(rows, x, (*y).st);
auto itr = go_right(rows, x, (*y).st);
if((*it).nd == -1 && (*itr).nd == -1) {
cerr<<' '<<max((*x).nd, h-(*x).nd-1)<<'\n';
return max((*x).nd, h-(*x).nd-1);
}
if((*it).nd == -1) {
int res1 = (*x).nd;
int res2 = (*itr).nd - (*x).nd;
res2 += solve(itr, y, !turn);
cerr<<' '<<max(res1, res2)<<'\n';
return max(res1, res2);
}
if((*itr).nd == -1) {
int res1 = h-(*x).nd-1;
int res2 = (*x).nd - (*it).nd;
res2 += solve(it, y, !turn);
cerr<<' '<<max(res1, res2)<<'\n';
return max(res1, res2);
}
if(min((*it).st, (*itr).st) > max_b) {
int res1 = (*x).nd - (*it).nd + max((*y).nd, w-(*y).nd-1);
int res2 = (*itr).nd - (*x).nd + max((*y).nd, w-(*y).nd-1);
cerr<<' '<<max(res1, res2)<<'\n';
return max(res1, res2);
}
if((*it).st < (*itr).st) {
int res = (*x).nd - (*it).nd;
res += solve(it, y, !turn);
cerr<<' '<<res<<'\n';
return res;
}
else {
int res = (*itr).nd - (*x).nd;
res += solve(itr, y, !turn);
cerr<<' '<<res<<'\n';
return res;
}
}
else {
auto it = go_left(colns, y, (*x).st);
auto itr = go_right(colns, y, (*x).st);
if((*it).nd == -1 && (*itr).nd == -1) {
cerr<<' '<<max((*y).nd, w-(*y).nd-1)<<'\n';
return max((*y).nd, w-(*y).nd-1);
}
if((*it).nd == -1) {
int res1 = (*y).nd;
int res2 = (*itr).nd - (*y).nd;
res2 += solve(x, itr, !turn);
cerr<<' '<<max(res1, res2)<<'\n';
return max(res1, res2);
}
if((*itr).nd == -1) {
int res1 = w-(*y).nd-1;
int res2 = (*y).nd - (*it).nd;
res2 += solve(x, it, !turn);
cerr<<' '<<max(res1, res2)<<'\n';
return max(res1, res2);
}
if(min((*it).st, (*itr).st) > max_a) {
int res1 = (*y).nd - (*it).nd + max((*x).nd, h-(*x).nd-1);
int res2 = (*itr).nd - (*y).nd + max((*x).nd, h-(*x).nd-1);
cerr<<' '<<max(res1, res2)<<'\n';
return max(res1, res2);
}
if((*it).st < (*itr).st) {
int res = (*y).nd - (*it).nd;
res += solve(x, it, !turn);
cerr<<' '<<res<<'\n';
return res;
}
else {
int res = (*itr).nd - (*y).nd;
res += solve(x, itr, !turn);
cerr<<' '<<res<<'\n';
return res;
}
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>h>>w>>q;
for(int i=0; i<h; ++i) {
cin>>a[i];
max_a = max(max_a, a[i]);
}
for(int i=0; i<w; ++i) {
cin>>b[w-i-1];
max_b = max(max_b, b[i]);
}
while(q--) {
int s, t; cin>>s>>t;
t = w-t+1;
int res = 0;
init();
/// Left
auto S = rows.begin()+s;
auto T = colns.begin()+t;
auto it = go_left(rows, S, (*T).st);
if((*it).nd==-1) {
res = max(res, (*S).nd);
}
else {
int dist = (*S).nd - (*it).nd;
res = max(res, dist+solve(it, T, 1));
}
init();
/// Right
S = rows.begin()+s;
T = colns.begin()+t;
it = go_right(rows, S, (*T).st);
if((*it).nd==-1) {
res = max(res, h-(*S).nd-1);
}
else {
int dist = (*it).nd - (*S).nd;
res = max(res, dist+solve(it, T, 1));
}
init();
/// Up
S = rows.begin()+s;
T = colns.begin()+t;
it = go_left(colns, T, (*S).st);
if((*it).nd==-1) {
res = max(res, (*T).nd);
}
else {
int dist = (*T).nd - (*it).nd;
res = max(res, dist+solve(S, it, 0));
}
init();
/// Down
S = rows.begin()+s;
T = colns.begin()+t;
it = go_right(colns, T, (*S).st);
if((*it).nd==-1) {
res = max(res, w-(*T).nd-1);
}
else {
int dist = (*it).nd - (*T).nd;
res = max(res, dist+solve(S, it, 0));
}
cout<<res<<'\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
