이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
enum {UP, LEFT, DOWN, RIGHT};
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};
const int MAXN = 65536;
const int lgMAXN = 16;
int H, W, Q;
int A[MAXN], B[MAXN];
//Am[i][j]: max of [i, i+2^j)
int Am[MAXN][lgMAXN], Bm[MAXN][lgMAXN];
int lg(int a)
{
return 31 - __builtin_clz(a);
}
void spinit()
{
for(int i=0; i<H; ++i) Am[i][0] = A[i];
for(int i=0; i<W; ++i) Bm[i][0] = B[i];
for(int j=1; j<lgMAXN; ++j)
{
for(int i=0; i<=H-(1<<j); ++i)
Am[i][j] = max(Am[i][j-1], Am[i+(1<<(j-1))][j-1]);
for(int i=0; i<=W-(1<<j); ++i)
Bm[i][j] = max(Bm[i][j-1], Bm[i+(1<<(j-1))][j-1]);
}
}
int MA(int s, int e)
{
int q = lg(e-s+1);
return max(Am[s][q], Am[e+1-(1<<q)][q]);
}
int MB(int s, int e)
{
int q = lg(e-s+1);
return max(Bm[s][q], Bm[e+1-(1<<q)][q]);
}
bool ins(int x, int y){ return 0<=x&&x<H&&0<=y&&y<W; }
map<tuple<int, int, int>, long long > M;
long long solve(int x, int y, int d)
{
auto it = M.find(make_tuple(x, y, d));
if(it != M.end()) return it->second;
if(d==UP)
{
int lo = -1; //pos
int hi = x; //imp
while(lo+1!=hi)
{
int mi = (lo+hi)>>1;
if(MA(mi, x-1) > B[y]) lo = mi;
else hi = mi;
}
//printf("%d %d UP -> %d %d\n", x, y, lo, y);
if(lo==-1) return M[{x, y, d}] = x;
else return M[{x, y, d}] = (x-lo) +
max(solve(lo, y, LEFT), solve(lo, y, RIGHT));
}
if(d==DOWN)
{
int lo = x; //imp
int hi = H; //pos
while(lo+1!=hi)
{
int mi = (lo+hi)>>1;
if(MA(x+1, mi) > B[y]) hi = mi;
else lo = mi;
}
//printf("%d %d DOWN -> %d %d\n", x, y, hi, y);
if(hi == H) return M[{x, y, d}] = H-1-x;
else return M[{x, y, d}] = (hi-x) +
max(solve(hi, y, LEFT), solve(hi, y, RIGHT));
}
if(d==LEFT)
{
int lo = -1; //pos
int hi = y; //imp
while(lo+1!=hi)
{
int mi = (lo+hi)>>1;
if(MB(mi, y-1) > A[x]) lo = mi;
else hi = mi;
}
//printf("%d %d LEFT -> %d %d\n", x, y, x, lo);
if(lo == -1) return M[{x, y, d}] = y;
else return M[{x, y, d}] = (y-lo) +
max(solve(x, lo, UP), solve(x, lo, DOWN));
}
if(d==RIGHT)
{
//puts("HELLO!");
int lo = y; //imp
int hi = W; //pos
while(lo+1!=hi)
{
int mi = (lo+hi)>>1;
if(MB(y+1, mi) > A[x]) hi = mi;
else lo = mi;
}
//printf("%d %d RIGHT -> %d %d\n", x, y, x, hi);
//puts("BYE!");
if(hi == W) return M[{x, y, d}] = W-1-y;
else return M[{x, y, d}] = (hi-y) +
max(solve(x, hi, UP), solve(x, hi, DOWN));
}
assert(false);
}
int main()
{
scanf("%d%d%d", &H, &W, &Q);
for(int i=0; i<H; ++i)
scanf("%d", A+i);
for(int i=0; i<W; ++i)
scanf("%d", B+i);
spinit();
while(Q--)
{
int S, T; scanf("%d%d", &S, &T); --S; --T;
long long ans = 0;
for(int d=0; d<4; ++d)
ans = max(ans, solve(S, T, d));
printf("%lld\n", ans);
}
}
컴파일 시 표준 에러 (stderr) 메시지
abduction2.cpp: In function 'int main()':
abduction2.cpp:117:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &H, &W, &Q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
abduction2.cpp:119:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", A+i);
~~~~~^~~~~~~~~~~
abduction2.cpp:121:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", B+i);
~~~~~^~~~~~~~~~~
abduction2.cpp:125:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int S, T; scanf("%d%d", &S, &T); --S; --T;
~~~~~^~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |