Submission #593445

#TimeUsernameProblemLanguageResultExecution timeMemory
593445cheissmartBodyguard (JOI21_bodyguard)C++14
0 / 100
25039 ms764464 KiB
#include <bits/stdc++.h> #define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0); #define F first #define S second #define V vector #define PB push_back #define EB emplace_back #define MP make_pair #define SZ(v) int((v).size()) #define ALL(v) (v).begin(), (v).end() using namespace std; typedef long long ll; typedef pair<int, int> pi; typedef V<int> vi; string _reset = "\u001b[0m", _yellow = "\u001b[33m", _bold = "\u001b[1m"; void DBG() { cerr << "]" << _reset << endl; } template<class H, class...T> void DBG(H h, T ...t) { cerr << to_string(h); if(sizeof ...(t)) cerr << ", "; DBG(t...); } #ifdef CHEISSMART #define debug(...) cerr << _yellow << _bold << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__) #else #define debug(...) #endif const int INF = 1e9 + 7; struct DS { V<pair<ll, ll>> tt; void insert(ll m, ll b) { tt.EB(m, b); } ll qry(ll x) { ll mx = 0; for(auto[m, b]:tt) { mx = max(mx, m * x + b); } return mx; } }; void claim(bool b) { if(!b) while(1); } signed main() { IO_OP; int n, q; cin >> n >> q; V<pair<pair<pi, pi>, int>> ev; vi xs, ys; for(int i = 0; i < n; i++) { int t, x, y, c, d; cin >> t >> x >> y >> c, d = abs(x - y); claim(c % 2 == 0); c /= 2; pi a = {t + x, t - x}; pi b = {t + d + y, t + d - y}; ev.EB(MP(a, b), c); xs.PB(a.F), ys.PB(a.S); xs.PB(b.F), ys.PB(b.S); } sort(ALL(xs)), xs.resize(unique(ALL(xs)) - xs.begin()); sort(ALL(ys)), ys.resize(unique(ALL(ys)) - ys.begin()); V<vi> dx, dy; dx = dy = V<vi>(SZ(xs), vi(SZ(ys))); V<V<ll>> dp = V<V<ll>>(SZ(xs), V<ll>(SZ(ys))); for(auto[pab, c]:ev) { auto[a, b] = pab; a.F = lower_bound(ALL(xs), a.F) - xs.begin(); a.S = lower_bound(ALL(ys), a.S) - ys.begin(); b.F = lower_bound(ALL(xs), b.F) - xs.begin(); b.S = lower_bound(ALL(ys), b.S) - ys.begin(); claim((a.F == b.F || a.S == b.S) && a != b); if(a.F == b.F) { assert(a.S <= b.S); for(int i = a.S; i < b.S; i++) dy[a.F][i] = max(dy[a.F][i], c); } else { assert(a.F < b.F); for(int i = a.F; i < b.F; i++) dx[i][a.S] = max(dx[i][a.S], c); } } for(int i = SZ(xs) - 1; i >= 0; i--) { for(int j = SZ(ys) - 1; j >= 0; j--) { if(i + 1 < SZ(xs)) dp[i][j] = max(dp[i][j], dp[i + 1][j] + 1LL * dx[i][j] * (xs[i + 1] - xs[i])); if(j + 1 < SZ(ys)) dp[i][j] = max(dp[i][j], dp[i][j + 1] + 1LL * dy[i][j] * (ys[j + 1] - ys[j])); } } V<V<V<pair<pi, int>>>> qq(SZ(xs), V<V<pair<pi, int>>>(SZ(ys))); V<ll> ans(q); for(int i = 0; i < q; i++) { int t, x; cin >> t >> x; pi a = {t + x, t - x}; int he = lower_bound(ALL(xs), a.F) - xs.begin(); int be = lower_bound(ALL(ys), a.S) - ys.begin(); if(he < SZ(xs) && be < SZ(ys)) { qq[he][be].EB(a, i); } } for(int j = 0; j < SZ(ys); j++) { DS ds; for(int i = SZ(xs) - 1; i >= 0; i--) { int c = j ? dy[i][j - 1] : 0; ds.insert(c, dp[i][j]); for(auto[a, qi]:qq[i][j]) ans[qi] = max(ans[qi], ds.qry(ys[j] - a.S)); } } for(int i = 0; i < SZ(xs); i++) { DS ds; for(int j = SZ(ys) - 1; j >= 0; j--) { int c = i ? dx[i - 1][j] : 0; ds.insert(c, dp[i][j]); for(auto[a, qi]:qq[i][j]) ans[qi] = max(ans[qi], ds.qry(xs[i] - a.F)); } } for(int i = 0; i < q; i++) cout << ans[i] << '\n'; }

Compilation message (stderr)

bodyguard.cpp: In member function 'll DS::qry(ll)':
bodyguard.cpp:40:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |   for(auto[m, b]:tt) {
      |           ^
bodyguard.cpp: In function 'int main()':
bodyguard.cpp:77:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |  for(auto[pab, c]:ev) {
      |          ^
bodyguard.cpp:78:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   78 |   auto[a, b] = pab;
      |       ^
bodyguard.cpp:119:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  119 |    for(auto[a, qi]:qq[i][j])
      |            ^
bodyguard.cpp:128:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  128 |    for(auto[a, qi]:qq[i][j])
      |            ^
#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...