제출 #427860

#제출 시각아이디문제언어결과실행 시간메모리
427860CodePlatinaBodyguard (JOI21_bodyguard)C++17
0 / 100
25172 ms1249880 KiB
#include <bits/stdc++.h> #define pii pair<int, int> #define pll pair<long long, long long> #define piii pair<int, pii> #define tiii tuple<int, int, int> #define tiiii tuple<int, int, int, int> #define ff first #define ss second #define ee ss.ff #define rr ss.ss using namespace std; struct line { long long a, b; line(void) : a(0), b(-(long long)8e18-7) {} long long eval(long long x) { return a * x + b; } }; struct Node { line x; int l, r; Node(void) : x(), l(-1), r(-1) {} }; vector<Node> lct; int ins(int ind, long long s, long long e, line val) { if(ind == -1) { ind = (int)lct.size(); lct.emplace_back(); } long long mid = s + e >> 1; line up = lct[ind].x; line dn = val; if(up.eval(s) < dn.eval(s)) swap(up, dn); if(up.eval(e) > dn.eval(e)) { lct[ind].x = up; return ind; } else if(up.eval(mid) < dn.eval(mid)) { lct[ind].x = dn; lct[ind].l = ins(lct[ind].l, s, mid, up); return ind; } else { lct[ind].x = up; lct[ind].r = ins(lct[ind].r, mid + 1, e, dn); return ind; } } long long qry(int ind, long long s, long long e, long long x) { if(ind == -1) return -(long long)8e18-7; long long mid = s + e >> 1; if(x < mid) return max(lct[ind].x.eval(x), qry(lct[ind].l, s, mid, x)); else if(x > mid) return max(lct[ind].x.eval(x), qry(lct[ind].r, mid + 1, e, x)); return lct[ind].x.eval(x); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // freopen("in.txt", "r", stdin); int n, T; cin >> n >> T; tiiii A[n]; for(auto &[a, b, c, d] : A) cin >> a >> b >> c >> d; vector<long long> prX, prY; for(auto &[a, b, c, d] : A) { if(b < c) { prX.push_back(1ll * a + b); prX.push_back(1ll * a - b + 2 * c); prY.push_back(1ll * a - b); } else { prX.push_back(1ll * a + b); prY.push_back(1ll * a + b - 2 * c); prY.push_back(1ll * a - b); } } prX.push_back((long long)4e9+7); prX.push_back(-(long long)4e9-7); prX.push_back((long long)4e9+7); prY.push_back(-(long long)4e9-7); sort(prX.begin(), prX.end()); sort(prY.begin(), prY.end()); prX.resize(unique(prX.begin(), prX.end()) - prX.begin()); prY.resize(unique(prY.begin(), prY.end()) - prY.begin()); int N = prX.size(), M = prY.size(); int CX[N + 1][M + 1]{}, CY[N + 1][M + 1]{}; for(auto &[a, b, c, d] : A) { if(b < c) { int x1 = lower_bound(prX.begin(), prX.end(), 1ll * a + b) - prX.begin(); int x2 = lower_bound(prX.begin(), prX.end(), 1ll * a - b + 2 * c) - prX.begin(); int y = lower_bound(prY.begin(), prY.end(), 1ll * a - b) - prY.begin(); for(int j = x1; j < x2; ++j) CX[j][y] = max(CX[j][y], d / 2); } else { int x = lower_bound(prX.begin(), prX.end(), 1ll * a + b) - prX.begin(); int y1 = lower_bound(prY.begin(), prY.end(), 1ll * a - b) - prY.begin(); int y2 = lower_bound(prY.begin(), prY.end(), 1ll * a + b - 2 * c) - prY.begin(); for(int j = y1; j < y2; ++j) CY[x][j] = max(CY[x][j], d / 2); } } long long dp[N + 1][M + 1]{}; for(int i = N; i >= 0; --i) { for(int j = M; j >= 0; --j) { if(i < N) dp[i][j] = max(dp[i][j], dp[i + 1][j] + 1ll * CX[i][j] * (prX[i + 1] - prX[i])); if(j < M) dp[i][j] = max(dp[i][j], dp[i][j + 1] + 1ll * CY[i][j] * (prY[j + 1] - prY[j])); } } // for(int i = 0; i <= N; ++i) // { // for(int j = 0; j <= M; ++j) // cout << dp[i][j] << ' '; // cout << endl; // } vector<pll> lsX[N + 1][M + 1], lsY[N + 1][M + 1]; for(int i = 0; i < T; ++i) { int x, y; cin >> x >> y; int xi = lower_bound(prX.begin(), prX.end(), x + y) - prX.begin(); int yi = lower_bound(prY.begin(), prY.end(), x - y) - prY.begin(); lsX[xi][yi].push_back({prX[xi] - x - y, i}); lsY[xi][yi].push_back({prY[yi] - x + y, i}); } long long ans[T]{}; for(int i = 1; i <= N; ++i) { lct.clear(); lct.emplace_back(); for(int j = M; j >= 0; --j) { line tmp; tmp.a = CX[i - 1][j]; tmp.b = dp[i][j]; ins(0, -(long long)4e9-7, (long long)4e9+7, tmp); for(auto [x, q] : lsX[i][j]) ans[q] = max(ans[q], qry(0, -(long long)4e9-7, (long long)4e9+7, x)); } } for(int j = 1; j <= M; ++j) { lct.clear(); lct.emplace_back(); for(int i = N; i >= 0; --i) { line tmp; tmp.a = CY[i][j - 1]; tmp.b = dp[i][j]; ins(0, -(long long)4e9-7, (long long)4e9+7, tmp); for(auto [x, q] : lsY[i][j]) ans[q] = max(ans[q], qry(0, -(long long)4e9-7, (long long)4e9+7, x)); } } for(auto i : ans) cout << i << '\n'; }

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

bodyguard.cpp: In function 'int ins(int, long long int, long long int, line)':
bodyguard.cpp:37:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |     long long mid = s + e >> 1;
      |                     ~~^~~
bodyguard.cpp: In function 'long long int qry(int, long long int, long long int, long long int)':
bodyguard.cpp:63:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |     long long mid = s + e >> 1;
      |                     ~~^~~
#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...