제출 #105721

#제출 시각아이디문제언어결과실행 시간메모리
105721Pro_ktmr유괴 2 (JOI17_abduction2)C++14
100 / 100
4966 ms129608 KiB
#include"bits/stdc++.h" using namespace std; #define LL long long #define PB push_back #define MP make_pair #define int long long struct SegmentTree{ private: int N; vector<int> node; public: void init(int n){ N = 1; while(N < n) N *= 2; for(int i=0; i<2*N-1; i++) node.PB(0); } void update(int k, int x){ k += N-1; node[k] = x; while(k > 0){ k = (k-1)/2; node[k] = max(node[2*k+1], node[2*k+2]); } } int findL(int a, int b, int x, int k=0, int l=0, int r=-1){ if(r == -1) r = N; if(r <= a || b <= l) return INT_MAX; if(r-l == 1){ if(node[k] > x) return k-(N-1); else return INT_MAX; } if(a <= l && r <= b){ if(node[2*k+1] > x) return findL(a, b, x, 2*k+1, l, (l+r)/2); if(node[2*k+2] > x) return findL(a, b, x, 2*k+2, (l+r)/2, r); return INT_MAX; } else{ return min( findL(a, b, x, 2*k+1, l, (l+r)/2), findL(a, b, x, 2*k+2, (l+r)/2, r) ); } } int findR(int a, int b, int x, int k=0, int l=0, int r=-1){ if(r == -1) r = N; if(r <= a || b <= l) return INT_MIN; if(r-l == 1){ if(node[k] > x) return k-(N-1); else return INT_MIN; } if(a <= l && r <= b){ if(node[2*k+2] > x) return findR(a, b, x, 2*k+2, (l+r)/2, r); if(node[2*k+1] > x) return findR(a, b, x, 2*k+1, l, (l+r)/2); return INT_MIN; } else{ return max( findR(a, b, x, 2*k+1, l, (l+r)/2), findR(a, b, x, 2*k+2, (l+r)/2, r) ); } } void print(){ for(int i=0; i<node.size(); i++) cout << node[i] << " "; cout << endl; } }; int H,W,Q,A[50000],B[50000]; SegmentTree a,b; map<pair<int,int>,int> dp; /* 3 1 2 0 */ int solve(int Y, int X, int moto){ //moto-10key if(moto == -1){ int ans = 0; if(b.findR(0, X, A[Y]) != INT_MIN) ans = max(ans, solve(Y, b.findR(0, X, A[Y]), 2) +X-b.findR(0, X, A[Y])); else ans = max(ans, X); if(b.findL(X+1, W, A[Y]) != INT_MAX) ans = max(ans, solve(Y, b.findL(X+1, W, A[Y]), 1) +b.findL(X+1, W, A[Y])-X); else ans = max(ans, W-X-1); if(a.findR(0, Y, B[X]) != INT_MIN) ans = max(ans, solve(a.findR(0, Y, B[X]), X, 0) +Y-a.findR(0, Y, B[X])); else ans = max(ans, Y); if(a.findL(Y+1, H, B[X]) != INT_MAX) ans = max(ans, solve(a.findL(Y+1, H, B[X]), X, 3) +a.findL(Y+1, H, B[X])-Y); else ans = max(ans, H-Y-1); return ans; } if(dp.count({Y,X}) == 1) return dp[{Y,X}]; int ans = 0; if(A[Y] > B[X]){ if(b.findR(0, X, A[Y]) != INT_MIN) ans = max(ans, solve(Y, b.findR(0, X, A[Y]), 2) +X-b.findR(0, X, A[Y])); else ans = max(ans, X); if(b.findL(X+1, W, A[Y]) != INT_MAX) ans = max(ans, solve(Y, b.findL(X+1, W, A[Y]), 1) +b.findL(X+1, W, A[Y])-X); else ans = max(ans, W-X-1); } else{ if(a.findR(0, Y, B[X]) != INT_MIN) ans = max(ans, solve(a.findR(0, Y, B[X]), X, 0) +Y-a.findR(0, Y, B[X])); else ans = max(ans, Y); if(a.findL(Y+1, H, B[X]) != INT_MAX) ans = max(ans, solve(a.findL(Y+1, H, B[X]), X, 3) +a.findL(Y+1, H, B[X])-Y); else ans = max(ans, H-Y-1); } //cout << Y << " " << X << " " << moto << " " << ans << endl; return dp[{Y,X}] = ans; } signed main(){ cin >> H >> W >> Q; a.init(H); for(int i=0; i<H; i++){ cin >> A[i]; a.update(i, A[i]); } b.init(W); for(int i=0; i<W; i++){ cin >> B[i]; b.update(i, B[i]); } for(int i=0; i<Q; i++){ int Y,X; cin >> Y >> X; Y--; X--; cout << solve(Y, X, -1) << endl; } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

abduction2.cpp: In member function 'void SegmentTree::print()':
abduction2.cpp:60:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<node.size(); i++) cout << node[i] << " ";
                ~^~~~~~~~~~~~
#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...