Submission #402010

#TimeUsernameProblemLanguageResultExecution timeMemory
402010dooweyBodyguard (JOI21_bodyguard)C++14
7 / 100
4954 ms1059596 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; #define fi first #define se second #define mp make_pair #define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); const int N = 2810; const int M = N * 2; const ll inf = (ll)1e18; ll X[N], Y[N]; ll XX[N], YY[N]; ll val[N]; vector<ll> xc, yc; ll XI[M][M]; ll YI[M][M]; ll dp[M][M]; const int Q = (int)3e6 + 10; struct query{ ll xcor; ll ycor; int idx; }; vector<query> qq[M][M]; ll outp[Q]; struct line{ ll ai; ll bi; ll lim; }; ll divv(ll x, ll y){ return (x / y - (x%y != 0 && (x^y) < 0)); } ll inter(line p1, line p2){ return divv(p1.bi - p2.bi, p2.ai - p1.ai); } struct hull{ vector<line> st; void add_line(line qq){ while(!st.empty() && qq.ai >= st.back().ai) st.pop_back(); ll p1, p2; while(st.size() >= 2){ p1 = inter(st[st.size() - 1], qq); p2 = inter(st[st.size() - 2], qq); if(p1 < p2) break; st.pop_back(); } if(st.size() > 0) st[st.size() - 1].lim = inter(st[st.size() - 1], qq); qq.lim = -(ll)1e18; st.push_back(qq); } ll bins(ll pp){ ll soln = 0; for(auto x : st){ soln = max(soln, x.ai * 1ll * pp + x.bi); } return soln; } }; int main(){ fastIO; int n, q; cin >> n >> q; ll start, en, tim; for(int i = 1; i <= n; i ++ ){ cin >> tim >> start >> en >> val[i]; start *= 2ll; tim *= 2ll; en *= 2ll; X[i] = tim + start; Y[i] = tim - start; tim += abs(en - start); XX[i] = tim + en; YY[i] = tim - en; xc.push_back(X[i]); yc.push_back(Y[i]); xc.push_back(XX[i]); yc.push_back(YY[i]); } sort(xc.begin(), xc.end()); sort(yc.begin(), yc.end()); xc.resize(unique(xc.begin(), xc.end()) - xc.begin()); yc.resize(unique(yc.begin(), yc.end()) - yc.begin()); int nn = xc.size(); int mm = yc.size(); int iq; for(int i = 1; i <= n; i ++ ){ X[i] = lower_bound(xc.begin(), xc.end(), X[i]) - xc.begin(); Y[i] = lower_bound(yc.begin(), yc.end(), Y[i]) - yc.begin(); XX[i]= lower_bound(xc.begin(), xc.end(), XX[i]) - xc.begin(); YY[i] = lower_bound(yc.begin(), yc.end(), YY[i]) - yc.begin(); if(X[i] == XX[i]){ for(int j = Y[i] + 1; j <= YY[i]; j ++ ){ YI[X[i]][j] = max(YI[X[i]][j], val[i]); } } else{ for(int j = X[i] + 1; j <= XX[i]; j ++ ){ XI[j][Y[i]] = max(XI[j][Y[i]], val[i]); } } } for(int x = nn - 1; x >= 0 ; x -- ){ for(int y = mm - 1; y >= 0; y -- ){ if(x + 1 < nn) dp[x][y] = max(dp[x][y], dp[x + 1][y] + (xc[x + 1] - xc[x]) * 1ll * XI[x + 1][y]); if(y + 1 < mm) dp[x][y] = max(dp[x][y], dp[x][y + 1] + (yc[y + 1] - yc[y]) * 1ll * YI[x][y + 1]); } } ll xa, ya; int xlow, ylow; ll big; ll cc; for(int iq = 1; iq <= q; iq ++ ){ cin >> tim >> start; tim *= 2ll; start *= 2ll; xa = tim + start; ya = tim - start; xlow = lower_bound(xc.begin(), xc.end(), xa) - xc.begin(); ylow = lower_bound(yc.begin(), yc.end(), ya) - yc.begin(); if(xlow == nn || ylow == mm){ outp[iq] = 0; continue; } qq[xlow][ylow].push_back({xa, ya, iq}); big = 0; /* for(int j = xlow; j < nn; j ++ ){ big = max(big, dp[j][ylow] + (yc[ylow] - ya) * 1ll * YI[j][ylow]); } for(int j = ylow; j < mm ; j ++ ){ big = max(big, dp[xlow][j] + (xc[xlow] - xa) * 1ll * XI[xlow][j]); } */ } for(int qy = 0; qy < mm; qy ++ ){ hull ash; for(int qx = nn - 1; qx >= 0; qx -- ){ ash.add_line({YI[qx][qy],dp[qx][qy],-(ll)1e18}); for(auto xx : qq[qx][qy]){ outp[xx.idx] = max(outp[xx.idx], ash.bins(yc[qy] - xx.ycor)); } } } for(int qx = 0; qx < nn; qx ++ ){ hull ash; for(int qy = mm - 1; qy >= 0; qy -- ){ ash.add_line({XI[qx][qy], dp[qx][qy], -(ll)1e18}); for(auto xx : qq[qx][qy]){ outp[xx.idx] = max(outp[xx.idx], ash.bins(xc[qx] - xx.xcor)); } } } for(int iq = 1; iq <= q; iq ++ ){ cout << outp[iq]/4ll << "\n"; } return 0; }

Compilation message (stderr)

bodyguard.cpp: In function 'int main()':
bodyguard.cpp:104:9: warning: unused variable 'iq' [-Wunused-variable]
  104 |     int iq;
      |         ^~
bodyguard.cpp:131:8: warning: variable 'big' set but not used [-Wunused-but-set-variable]
  131 |     ll big;
      |        ^~~
bodyguard.cpp:132:8: warning: unused variable 'cc' [-Wunused-variable]
  132 |     ll cc;
      |        ^~
#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...