#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#define owo(i,a, b) for(auto i=(a);i<(b); ++i)
#define uwu(i,a, b) for(auto i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"ayaya~"<<endl
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<ttgl, null_type,less<ttgl>, rb_tree_tag,tree_order_statistics_node_update>*/
using ll = long long;
using ld = long double;
const ll MOD = 1000000007;
const ll root = 62;
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
const double PI = atan(1);
const double eps = 1e-10;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
const int mxN = 50001;
map<array<int, 3>, ll> mp;
int H[mxN][2][16];
int W[mxN][2][16];
int h, w, q;
ll solve(int x, int y, int dir) {
if(mp.find({x, y, dir})!=mp.end())return mp[{x, y, dir}];
ll res = 0;
if(dir==0) {
int dxl = x-1;
int dxr = x+1;
int mx = W[y][0][0];
uwu(lg, 16, 0) {
//cout<<dxl<<" "<<dxr<<" x"<<endl;
if(H[dxl][0][lg] <= mx) {
dxl = max(0, dxl - (1<<lg));
}
if(H[dxr][1][lg] <= mx) {
dxr = min(h+1, dxr + (1<<lg));
}
}
//cout<<x<<" "<<y<<" "<<dir<<" "<<mx<<" "<<dxl<<" "<<dxr<<"\n";
if(dxl == 0) res = max(res, (ll)x - 1);
else res = max(res, x - dxl + solve(dxl, y, 1));
if(dxr == h+1) res = max(res, (ll)h - x);
else res = max(res, dxr - x + solve(dxr, y, 1));
}else {
int dyl = y-1;
int dyr = y+1;
int mx = H[x][0][0];
uwu(lg, 16, 0) {
//cout<<dyl<<" "<<dyr<<" y"<<endl;
if(W[dyl][0][lg] <= mx) {
dyl = max(0, dyl - (1<<lg));
}
if(W[dyr][0][lg] <= mx) {
dyr = min(w+1, dyr + (1<<lg));
}
}
if(dyl == 0) res = max(res, (ll)y - 1);
else res = max(res, y - dyl + solve(x, dyl, 0));
if(dyr == w+1) res = max(res, (ll)w - y);
else res = max(res, dyr - y + solve(x, dyr, 0));
}
//cout<<x<<" "<<y<<" "<<dir<<" "<<res<<"\n";
return mp[{x, y, dir}] = res;
}
int main() {
//freopen("file.in", "r", stdin);
//freopen("file.out", "w", stdout);
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
cin.tie(0)->sync_with_stdio(0);
cin>>h>>w>>q;
owo(i, 1, h+1) {
cin>>H[i][0][0];
H[i][1][0] = H[i][0][0];
}
owo(i, 1, w+1) {
cin>>W[i][0][0];
W[i][1][0] = W[i][0][0];
}
owo(lg, 1, 16) {
owo(dir, 0, 2) {
int sn = (dir ? 1 : -1);
owo(i, 1, h+1) {
int nval = i + sn*(1<<(lg-1));
nval = max(nval, 0);
nval = min(nval, h+1);
H[i][dir][lg] = max(H[i][dir][lg-1], H[nval][dir][lg-1]);
//cout<<i<<" "<<dir<<" "<<lg<<" "<<H[i][dir][lg]<<" H\n";
}
owo(i, 1, w+1) {
int nval = i + sn*(1<<(lg-1));
nval = max(nval, 0);
nval = min(nval, w+1);
W[i][dir][lg] = max(W[i][dir][lg-1], W[nval][dir][lg-1]);
//cout<<i<<" "<<dir<<" "<<lg<<" "<<W[i][dir][lg]<<" W\n";
}
}
}
int a, b;
while(q--) {
cin>>a>>b;
cout<<(max(solve(a, b, 0), solve(a, b, 1)))<<"\n";
//ayaya;
}
return 0;
}
Compilation message
abduction2.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
2 | #pragma GCC optimization ("O3")
|
abduction2.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
3 | #pragma GCC optimization ("unroll-loops")
|
| # |
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 |
Runtime error |
600 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 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 |
- |
