Submission #1209708

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209708		abczz	Bodyguard (JOI21_bodyguard)	C++20	100 / 100	4705 ms	1402324 KiB

bodyguard

#include <iostream>
#include <map>
#include <set>
#include <vector>
#define ll long long
#define ld long double

using namespace std;

map <ll, ll> mp, mp2;
array <ll, 4> A[2800];
vector <ll> X, Y;
vector <array<ll, 3>> VR[5600], VC[5600];
vector <ll> Q[5600][5600];
ll n, q, t, a, b, c, x, y, f, R[5600][5600], U[5600][5600], dp[5605][5605], F[3000000], QX[3000000], QY[3000000];

struct Line{
  mutable ll m, c;
  mutable ld d;
  bool operator<(const Line &o) const {return (o.m == -1e18 ? d < o.d : m < o.m);}
};
struct LineContainer : multiset<Line, less<>> {
  ld eps = 1e-8;
  bool isect(iterator x, iterator y) {
    if (y == end()) {
      x->d = 1e18;
      return 0;
    }
    if (x->m == y->m) x->d = x->c > y-> c ? 1e18 : -1e18;
    else x->d = (ld)(y->c - x->c)/(x->m - y->m);
    return (x->d > y->d || abs(x->d - y->d) < eps);
  }
  void add(ll m, ll c) {
    auto z = insert({m, c, 0}), y = z++, x = y;
    while (isect(y, z)) z = erase(z);
    if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
    while ((y = x) != begin() && (--x)->d >= y->d) isect(x, erase(y));
  }
  ll query(ll x) {
    if (empty()) return 0;
    Line l = {-(ll)1e18, 0, (ld)x};
    auto it = lower_bound(l);
    return it->m * x + it->c;
  }
}LC;
struct SegTree{
  ll st[22400], lazy[22400];
  void init(ll sz) {
    for (int i=0; i<4*sz; ++i) st[i] = lazy[i] = 0;
  }
  void push(ll id) {
    st[id*2] = max(st[id*2], lazy[id]);
    st[id*2+1] = max(st[id*2+1], lazy[id]);
    lazy[id*2] = max(lazy[id*2], lazy[id]);
    lazy[id*2+1] = max(lazy[id*2+1], lazy[id]);
    lazy[id] = 0;
  }
  void update(ll id, ll l, ll r, ll ql, ll qr, ll w) {
    if (qr < l || r < ql) return;
    else if (ql <= l && r <= qr) {
      st[id] = max(st[id], w);
      lazy[id] = max(lazy[id], w);
      return;
    }
    push(id);
    ll mid = (l+r)/2;
    update(id*2, l, mid, ql, qr, w);
    update(id*2+1, mid+1, r, ql, qr, w);
  }
  void solve(ll id, ll l, ll r, ll ty, ll i) {
    if (l == r) {
      if (!ty) R[i][l] = st[id];
      else U[l][i] = st[id];
      return;
    }
    ll mid = (l+r)/2;
    push(id);
    solve(id*2, l, mid, ty, i);
    solve(id*2+1, mid+1, r, ty, i);
  }
}ST;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cin >> n >> q;
  for (int i=0; i<n; ++i) {
    for (int j=0; j<4; ++j) cin >> A[i][j];
    ++mp[A[i][0]+A[i][1]];
    ++mp2[A[i][0]-A[i][1]];
    ++mp[A[i][0]+abs(A[i][1]-A[i][2])+A[i][2]];
    ++mp2[A[i][0]+abs(A[i][1]-A[i][2])-A[i][2]];
  }
  for (auto [x, y] : mp) X.push_back(x), mp[x] = (ll)X.size()-1;
  for (auto [x, y] : mp2) Y.push_back(x), mp2[x] = (ll)Y.size()-1;
  for (int i=0; i<n; ++i) {
    if (A[i][1] < A[i][2]) {
      VR[mp2[A[i][0]-A[i][1]]].push_back({mp[A[i][0]+A[i][1]], mp[A[i][0]+abs(A[i][1]-A[i][2])+A[i][2]]-1, A[i][3]});
    }
    else {
      VC[mp[A[i][0]+A[i][1]]].push_back({mp2[A[i][0]-A[i][1]], mp2[A[i][0]+abs(A[i][1]-A[i][2])-A[i][2]]-1, A[i][3]});
    }
  }
  for (int i=0; i<mp2.size(); ++i) {
    ST.init(mp.size());
    for (auto [l, r, w] : VR[i]) {
      ST.update(1, 0, mp.size()-1, l, r, w);
    }
    ST.solve(1, 0, mp.size()-1, 0, i);
  }
  for (int i=0; i<mp.size(); ++i) {
    ST.init(mp2.size());
    for (auto [l, r, w] : VC[i]) {
      ST.update(1, 0, mp2.size()-1, l, r, w);
    }
    ST.solve(1, 0, mp2.size()-1, 1, i);
  }
  for (int i=mp2.size()-1; i>=0; --i) {
    for (int j=mp.size()-1; j>=0; --j) {
      if (j != mp.size()-1) dp[i][j] = max(dp[i][j], dp[i][j+1] + R[i][j] * (X[j+1]-X[j])/2);
      if (i != mp2.size()-1) dp[i][j] = max(dp[i][j], dp[i+1][j] + U[i][j] * (Y[i+1]-Y[i])/2);
    }
  }
  for (int i=0; i<q; ++i) {
    cin >> a >> b;
    QX[i] = a+b, QY[i] = a-b;
    auto it = lower_bound(X.begin(), X.end(), QX[i]);
    auto it2 = lower_bound(Y.begin(), Y.end(), QY[i]);
    if (it == X.end() || it2 == Y.end()) continue;
    a = it2-Y.begin(), b = it-X.begin();
    if (a == 0 && b == 0) F[i] = dp[0][0];
    else Q[a][b].push_back(i);
  }
  for (int i=1; i<mp2.size(); ++i) {
    LC.clear();
    ll cur = -1e18;
    for (int j=mp.size()-1; j>=0; --j) {
      if (U[i-1][j]) LC.add(-U[i-1][j], U[i-1][j] * Y[i] + 2*dp[i][j]);
      else cur = max(cur, 2*dp[i][j]);
      for (auto z : Q[i][j]) {
        F[z] = max(F[z], max(cur, LC.query(QY[z]))/2);
      }
    }
  }
  for (int i=1; i<mp.size(); ++i) {
    LC.clear();
    ll cur = -1e18;
    for (int j=mp2.size()-1; j>=0; --j) {
      if (R[j][i-1]) LC.add(-R[j][i-1], R[j][i-1] * X[i] + 2*dp[j][i]);
      else cur = max(cur, 2*dp[j][i]);
      for (auto z : Q[j][i]) {
        F[z] = max(F[z], max(cur, LC.query(QX[z]))/2);
      }
    }
  }
  for (int i=0; i<q; ++i) cout << F[i] << '\n';
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 52 / 52