| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 551938 | Lobo | Abduction 2 (JOI17_abduction2) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
// #define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 5e4+10;
int n, m, q, a[maxn], b[maxn];
map<int,int> mark[maxn][5], dp[maxn][5];
pair<int,int> mxalf[maxn][25], mxarg[maxn][25], mxblf[maxn][25], mxbrg[maxn][25];
//ver com 32 tambem
int mxblr(int l, int r) {
if(l > r) return -1;
int lg = 31-__builtin_clz(r-l+1);
auto ans = max(mxbrg[l][lg],mxblf[r][lg]);
return ans.fr;
}
int mxalr(int l, int r) {
if(l > r) return -1;
int lg = 31-__builtin_clz(r-l+1);
auto ans = max(mxarg[l][lg],mxalf[r][lg]);
return ans.fr;
}
//0 -> x aumenta, 1 -> x diminui e dobra para vertical
//2 -> y aumenta, 3 -> y diminui
//x -> M e y-> N
int cnt = 0;
int sol(int y, int x, int dir) {
if(mark[y][dir][x]) return dp[y][dir][x];
mark[y][dir][x] = 1;
if(dir == 0) {
//vou para um (x1,y) que b[x1] > a[y] e x1 > x
if(mxblr(x+1,m) < a[y]) {
return dp[y][dir][x] = m-x;
}
int l = x+1;
int r = m;
int ans = -1;
while(l <= r) {
int mid = (l+r)/2;
if(mxblr(x+1,mid) >= a[y]) {
ans = mid;
r = mid-1;
}
else {
l = mid+1;
}
}
return dp[y][dir][x] = ans-x+max(sol(y,ans,2),sol(y,ans,3));
}
else if(dir == 1) {
//vou para um (x1,y) que b[x1] > a[y] e x1 < x
if(mxblr(1,x-1) < a[y]) {
return dp[y][dir][x] = x-1;
}
int l = 1;
int r = x-1;
int ans = -1;
while(l <= r) {
int mid = (l+r)/2;
if(mxblr(mid,x-1) >= a[y]) {
ans = mid;
l = mid+1;
}
else {
r = mid-1;
}
}
return dp[y][dir][x] = x-ans+max(sol(y,ans,2),sol(y,ans,3));
}
else if(dir == 2) {
//vou para um (x,y1) que a[y1] > b[x] e y1 > y
if(mxalr(y+1,n) < b[x]) {
return dp[y][dir][x] = n-y;
}
int l = y+1;
int r = n;
int ans = -1;
while(l <= r) {
int mid = (l+r)/2;
if(mxalr(y+1,mid) >= b[x]) {
ans = mid;
r = mid-1;
}
else {
l = mid+1;
}
}
return dp[y][dir][x] = ans-y+max(sol(ans,x,0),sol(ans,x,1));
}
else {
//vou para um (x,y1) que a[y1] > b[x] e y1 < y
if(mxalr(1,y-1) < b[x]) {
return dp[y][dir][x] = y-1;
}
int l = 1;
int r = y-1;
int ans = -1;
while(l <= r) {
int mid = (l+r)/2;
if(mxalr(mid,y-1) >= b[x]) {
ans = mid;
l = mid+1;
}
else {
r = mid-1;
}
}
return dp[y][dir][x] = y-ans+max(sol(ans,x,0),sol(ans,x,1));
}
}
void solve() {
cin >> n >> m >> q;
for(int i = 1; i <= n; i++) {
cin >> a[i];
mxalf[i][0] = mxarg[i][0] = mp(a[i],i);
}
for(int i = 1; i <= m; i++) {
cin >> b[i];
mxblf[i][0] = mxbrg[i][0] = mp(b[i],i);
}
for(int pt = 1; pt <= 20; pt++) {
for(int i = 1; i <= n; i++) {
mxalf[i][pt] = max(mxalf[i][pt-1],mxalf[max(1LL,i-(1<<(pt-1)))][pt-1]);
}
}
for(int pt = 1; pt <= 20; pt++) {
for(int i = 1; i <= n; i++) {
mxarg[i][pt] = max(mxarg[i][pt-1],mxarg[min(n,i+(1<<(pt-1)))][pt-1]);
}
}
for(int pt = 1; pt <= 20; pt++) {
for(int i = 1; i <= m; i++) {
mxblf[i][pt] = max(mxblf[i][pt-1],mxblf[max(1LL,i-(1<<(pt-1)))][pt-1]);
}
}
for(int pt = 1; pt <= 20; pt++) {
for(int i = 1; i <= m; i++) {
mxbrg[i][pt] = max(mxbrg[i][pt-1],mxbrg[min(m,i+(1<<(pt-1)))][pt-1]);
}
}
while(q--) {
int y,x;
cin >> y >> x;
cout << max({sol(y,x,0),sol(y,x,1),sol(y,x,2),sol(y,x,3)}) << endl;
}
}
int32_t main() {
ios::sync_with_stdio(false); cin.tie(0);
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int tt = 1;
// cin >> tt;
while(tt--) {
solve();
}
}