Submission #530201

#TimeUsernameProblemLanguageResultExecution timeMemory
530201blueBodyguard (JOI21_bodyguard)C++17
7 / 100
4899 ms1154140 KiB
#include <iostream> #include <vector> #include <algorithm> #include <set> #include <cassert> #include <map> using namespace std; using ll = long long; using vll = vector<ll>; using vvll = vector<vll>; using vi = vector<int>; using vvi = vector<vi>; #define sz(x) int(x.size()) const int maxN = 2'800; int N; vll T(1 + maxN), A(1 + maxN), B(1 + maxN), C(1 + maxN); const int maxQ = 3'000'000; int Q; vll P(1 + maxQ), X(1 + maxQ); const ll INF = 1'000'000'000'000'000'000LL; struct lct { vll xv; vector<ll> a; vector<ll> b; lct(vll& xv_) { xv = xv_; a = b = vector<ll>((sz(xv) << 2) + 5, 0); } void insert(ll na, ll nb, int i, int xi, int xj) { if(na * xv[xi] + nb <= a[i] * xv[xi] + b[i] && na * xv[xj] + nb <= a[i] * xv[xj] + b[i]) return; // cerr << "inserting " << na << ' ' << nb << " over range " << xi << ' ' << xj << " : " << xv[xi] << ' ' << xv[xj] << '\n'; if(na * xv[xi] + nb >= a[i] * xv[xi] + b[i] && na * xv[xj] + nb >= a[i] * xv[xj] + b[i]) { a[i] = na; b[i] = nb; } else { if(na * xv[xi] * nb >= a[i] * xv[xi] + b[i]) { if(na * xv[(xi+xj)/2] + nb >= a[i] * xv[(xi+xj)/2] + b[i]) { insert(a[i], b[i], 2*i+1, (xi+xj)/2+1, xj); a[i] = na; b[i] = nb; } else { insert(na, nb, 2*i, xi, (xi+xj)/2); } } else { if(na * xv[(xi+xj)/2 + 1] + nb >= a[i] * xv[(xi+xj)/2+1] + b[i]) { insert(a[i], b[i], 2*i, xi, (xi+xj)/2); a[i] = na; b[i] = nb; } else insert(na, nb, 2*i+1, (xi+xj)/2+1, xj); } // if(na * xv[(xi+xj)/2] + nb >= a[i] * xv[(xi + xj)/2] + b[i]) // insert(na, nb, 2*i, xi, (xi+xj)/2); // insert(na, nb, 2*i+1, (xi+xj)/2+1, xj); // good = 0; // good[i] = 0; } } void insert(ll na, ll nb) { insert(na, nb, 1, 0, sz(xv) - 1); } ll query(ll x, int i, int xi, int xj) { ll curr_res = a[i] * x + b[i]; if(xi != xj) { if(x <= xv[(xi+xj)/2]) curr_res = max(curr_res, query(x, 2*i, xi, (xi+xj)/2)); else curr_res = max(curr_res, query(x, 2*i+1, (xi+xj)/2+1, xj)); } // if(good[i]) return a[i] * x + b[i]; // else if(x <= xv[(xi+xj)/2]) return query(x, 2*i, xi, (xi+xj)/2); // else return query(x, 2*i+1, (xi+xj)/2+1, xj); return curr_res; } ll query(ll x) { return query(x, 1, 0, sz(xv) - 1); } }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> N >> Q; for(int i = 1; i <= N; i++) { cin >> T[i] >> A[i] >> B[i] >> C[i]; T[i] *= 2; A[i] *= 2; B[i] *= 2; C[i] /= 2; } for(int j = 1; j <= Q; j++) { cin >> P[j] >> X[j]; P[j] *= 2; X[j] *= 2; } // if(Q > 40'000) assert(0); map<ll, ll> ypx_map, ymx_map; for(int i = 1; i <= N; i++) { ypx_map[T[i] + A[i]] = 0; ymx_map[T[i] - A[i]] = 0; ypx_map[(T[i] + abs(A[i] - B[i])) + B[i]] = 0; ymx_map[(T[i] + abs(A[i] - B[i])) - B[i]] = 0; // cerr << "ypx : " << T[i]+A[i] << ' ' << (T[i] + abs(A[i] - B[i])) + B[i] << '\n'; // cerr << "ymx : " << T[i] - A[i] << ' ' << (T[i] + abs(A[i] - B[i])) - B[i] << '\n'; } ll pct = 0, mct = 0; vll ypx{-2'000'000'002LL}; vll ymx{-2'000'000'002LL}; for(auto& z : ypx_map) { z.second = ++pct; ypx.push_back(z.first); } for(auto& z : ymx_map) { z.second = ++mct; ymx.push_back(z.first); } vi start_ypx(1 + N), start_ymx(1 + N), end_ypx(1 + N), end_ymx(1 + N); for(int i = 1; i <= N; i++) { start_ypx[i] = ypx_map[T[i] + A[i]]; start_ymx[i] = ymx_map[T[i] - A[i]]; end_ypx[i] = ypx_map[T[i] + abs(A[i] - B[i]) + B[i]]; end_ymx[i] = ymx_map[T[i] + abs(A[i] - B[i]) - B[i]]; } //i = ypx, j = ymx vvll horiz(1 + pct, vll(1 + mct, 0)); //(i, j) -> (i, j+1) vvll vert(1 + pct, vll(1 + mct, 0)); //(i, j) - (i+1, j) vvll horiz_basic(1 + pct, vll(1 + mct, 0)); //(i, j) -> (i, j+1) vvll vert_basic(1 + pct, vll(1 + mct, 0)); //(i, j) - (i+1, j) for(int i = 1; i <= N; i++) { if(B[i] < A[i]) { for(int j = start_ymx[i]; j < end_ymx[i]; j++) { // cerr << start_ypx[i] << " ! " << j << '\n'; horiz_basic[ start_ypx[i] ][j] = max(horiz_basic[ start_ypx[i] ][j], C[i]); // horiz[ start_ypx[i] ][j] = max(horiz[start_ypx[i]][j], (ymx[j+1] - ymx[j])/2 * C[i]); horiz[start_ypx[i]][j] = horiz_basic[start_ypx[i]][j] * (ymx[j+1] - ymx[j]) / 2; // cerr << ymx[j+1] << ' ' << ymx[j] << ' ' << C[i] << '\n'; // cerr << horiz[start_ypx[i]][j] << '\n'; } } else { for(int j = start_ypx[i]; j < end_ypx[i]; j++) { vert_basic[j][ start_ymx[i] ] = max(vert_basic[j][start_ymx[i]], C[i]); vert[j][ start_ymx[i] ] = (ypx[j+1] - ypx[j])/2 * vert_basic[ j ][ start_ymx[i] ]; } } } vvll dp(1 + pct, vll(1 + mct, 0)); for(int i = pct; i >= 1; i--) { for(int j = mct; j >= 1; j--) { if(i < pct) dp[i][j] = max(dp[i][j], dp[i+1][j] + vert[i][j]); if(j < mct) dp[i][j] = max(dp[i][j], dp[i][j+1] + horiz[i][j]); // cerr << i << ' ' << j << " : " << dp[i][j] << '\n'; } } vll res(1 + Q, 0); vi queries[1 + pct][1 + mct]; for(int j = 1; j <= Q; j++) { if(P[j] + X[j] > ypx.back()) continue; if(P[j] - X[j] > ymx.back()) continue; int plo = 1, phi = pct; while(plo != phi) { int mid = (plo + phi)/2; if(ypx[mid] < P[j] + X[j]) plo = mid+1; else phi = mid; } int mlo = 1, mhi = mct; while(mlo != mhi) { int mid = (mlo + mhi)/2; if(ymx[mid] < P[j] - X[j]) mlo = mid+1; else mhi = mid; } // cerr << plo << ' ' << mlo << " A \n"; queries[plo][mlo].push_back(j); } // cerr << "done\n"; // for(int pi = 1; pi <= pct; pi++) // { // cerr << ypx[pi] << " : "; // for(int mi = 1; mi <= mct; mi++) // { // cerr << dp[pi][mi] << ' '; // } // cerr << '\n'; // } for(int mi = 1; mi <= mct; mi++) { // cerr << "\n\n\n\n\n\n\n\n\n\n"; set<ll> xv; for(int pi = pct; pi >= 1; pi--) { for(int qr : queries[pi][mi]) { xv.insert((ymx[mi] - (P[qr] - X[qr]))/2); } } vll xvv; for(ll kv : xv) xvv.push_back(kv); if(xvv.empty()) continue; // lct CHT(xvv, 0, sz(xvv) - 1); lct CHT(xvv); // for(ll xvi : xvv) cerr << "xvi = " << xvi << '\n'; for(int pi = pct; pi >= 1; pi--) { // cerr << "\n\n\n\n\n"; // cerr << "pi mi = " << pi << ' ' << mi << '\n'; // if(mi == 3) // cerr << pi << ' ' << mi << " : " << "insert line " << ' ' << horiz_basic[pi][mi - 1] << ' ' << dp[pi][mi] << '\n'; CHT.insert(horiz_basic[pi][mi - 1], dp[pi][mi]); // cerr << "inserting " << horiz_basic[pi][mi-1] << ' ' << dp[pi][mi] << '\n'; for(int qr : queries[pi][mi]) { res[qr] = max(res[qr], CHT.query((ymx[mi] - (P[qr] - X[qr]))/2)); // cerr << "querying " << (ymx[mi] - (P[qr] - X[qr]))/2 << '\n'; // cerr << qr << " -> " << res[qr] << '\n'; // cerr << " ! " << res[qr] << '\n'; // cerr << "query = " << qr << ' ' << pi << ' ' << mi << '\n'; // cerr << "YMX = " << ymx[mi] << " - " << (P[qr] - X[qr]) << '\n'; // cerr << (ymx[mi] - (P[qr] - X[qr]))/2 << '\n'; // cerr << "x = " << (ymx[mi] - (P[qr] - X[qr]))/2 << "\n"; } } } // cerr << pct << " ; " << mct << '\n'; // cerr << "----------------------------------\n"; // cerr << "done 1\n"; for(int pi = 1; pi <= pct; pi++) { // cerr << "\n\n\n\n\n\n\n\n\n\n"; set<ll> xv; for(int mi = mct; mi >= 1; mi--) { for(int qr : queries[pi][mi]) { xv.insert((ypx[pi] - (P[qr] + X[qr]))/2); } } vll xvv; for(ll kv : xv) xvv.push_back(kv); if(xvv.empty()) continue; lct CHT(xvv); for(int mi = mct; mi >= 1; mi--) { // c CHT.insert(vert_basic[pi - 1][mi], dp[pi][mi]); // cerr << "ins done\n"; // cerr << "inserting : " << vert_basic[pi - 1][mi] << ", " << dp[pi][mi] << '\n'; for(int qr : queries[pi][mi]) { // cerr << "\n\n\n"; // cerr << "query = " << qr << " : " << pi << ' ' << mi << '\n'; res[qr] = max(res[qr], CHT.query((ypx[pi] - (P[qr] + X[qr]))/2)); // cerr << qr << " -> " << res[qr] << '\n'; // cerr << " ! " << res[qr] << '\n'; // cerr << "query done\n"; // cerr << pi << ' ' << mi << ' ' << qr << '\n'; // cerr << "query at " << CHT.query((ypx[pi] - (P[qr] + X[qr]))/2) << '\n'; } // c // cerr << "finished\n"; } } for(int j = 1; j <= Q; j++) cout << res[j] << '\n'; }
#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...