Submission #172325

#TimeUsernameProblemLanguageResultExecution timeMemory
172325ho94949Abduction 2 (JOI17_abduction2)C++17
44 / 100
454 ms35576 KiB
#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>, int > M; int 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)); } } 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; int ans = 0; for(int d=0; d<4; ++d) ans = max(ans, solve(S, T, d)); printf("%d\n", ans); } }

Compilation message (stderr)

abduction2.cpp: In function 'int solve(int, int, int)':
abduction2.cpp:113:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
abduction2.cpp: In function 'int main()':
abduction2.cpp:116: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:118:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", A+i);
         ~~~~~^~~~~~~~~~~
abduction2.cpp:120:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", B+i);
         ~~~~~^~~~~~~~~~~
abduction2.cpp:124: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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...