Submission #433000

#TimeUsernameProblemLanguageResultExecution timeMemory
433000CodePlatinaBodyguard (JOI21_bodyguard)C++17
0 / 100
7117 ms1106864 KiB
#define ON #ifdef ON #include <iostream> #include <vector> #include <tuple> #include <algorithm> #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; const long long INF = (long long)1e9 + 7; struct line { long long a, b; line(void) : a(0), b(0) {} long long eval(long long x) { return a * x + b; } }; 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 + INF); } else { prX.push_back(1ll * a + b); prY.push_back(1ll * a - b + INF); prY.push_back(1ll * a + b - 2 * c + INF); } } prX.push_back(INF * 3); prX.push_back(-1); prY.push_back(INF * 3); prY.push_back(-1); 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 + INF) - 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 + INF) - prY.begin(); int y2 = lower_bound(prY.begin(), prY.end(), 1ll * a + b - 2 * c + INF) - 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 + INF) - prY.begin(); lsX[xi][yi].push_back({prX[xi] - x - y, i}); lsY[xi][yi].push_back({prY[yi] - x + y - INF, i}); } vector<line> S; long long ans[T]{}; for(int i = 1; i <= N; ++i) { S.clear(); S.emplace_back(); for(int j = M; j >= 0; --j) { line tmp; tmp.a = CX[i - 1][j]; tmp.b = dp[i][j]; while(S.size() >= 2) { long long x = S[S.size() - 1].b - S[S.size() - 2].b; long long y = S[S.size() - 2].a - S[S.size() - 1].a; long long z = tmp.b - S[S.size() - 1].b; long long w = S[S.size() - 1].a - tmp.a; if(w <= 0 || x * w < y * z) S.pop_back(); else break; } if(S.back().b == tmp.b) S.back().a = max(S.back().a, tmp.a); else if(S.back().a <= tmp.a) S.back() = tmp; else S.push_back(tmp); for(auto [x, q] : lsX[i][j]) { int s = 0, e = S.size(); while(s + 1 < e) { int mid = s + e >> 1; long long y = S[mid].b - S[mid - 1].b; long long z = S[mid - 1].a - S[mid].a; if(x * z < y) s = mid; else e = mid; } ans[q] = max(ans[q], S[s].eval(x)); } } } for(int j = 1; j <= M; ++j) { S.clear(); S.emplace_back(); for(int i = N; i >= 0; --i) { line tmp; tmp.a = CY[i][j - 1]; tmp.b = dp[i][j]; while(S.size() >= 2) { long long x = S[S.size() - 1].b - S[S.size() - 2].b; long long y = S[S.size() - 2].a - S[S.size() - 1].a; long long z = tmp.b - S[S.size() - 1].b; long long w = S[S.size() - 1].a - tmp.a; if(w <= 0 || x * w < y * z) S.pop_back(); else break; } if(S.back().b == tmp.b) S.back().a = max(S.back().a, tmp.a); else if(S.back().a <= tmp.a) S.back() = tmp; else S.push_back(tmp); for(auto [x, q] : lsY[i][j]) { int s = 0, e = S.size(); while(s + 1 < e) { int mid = s + e >> 1; long long y = S[mid].b - S[mid - 1].b; long long z = S[mid - 1].a - S[mid].a; if(x * z < y) s = mid; else e = mid; } ans[q] = max(ans[q], S[s].eval(x)); } } } for(auto i : ans) cout << i << '\n'; } #else #include <iostream> #include <vector> #include <tuple> #include <algorithm> #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; 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); 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 = 0; i <= N; ++i) { for(int j = 0; j <= M; ++j) { for(auto [x, q] : lsX[i][j]) for(int k = j; k <= M; ++k) ans[q] = max(ans[q], dp[i][k] + 1ll * x * (i ? CX[i - 1][k] : 0)); for(auto [x, q] : lsY[i][j]) for(int k = i; k <= N; ++k) ans[q] = max(ans[q], dp[k][j] + 1ll * x * (j ? CY[k][j - 1] : 0)); } } for(auto i : ans) cout << i << '\n'; } #endif

Compilation message (stderr)

bodyguard.cpp: In function 'int main()':
bodyguard.cpp:142:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  142 |                     int mid = s + e >> 1;
      |                               ~~^~~
bodyguard.cpp:180:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  180 |                     int 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...