Submission #583400

#TimeUsernameProblemLanguageResultExecution timeMemory
583400AriaHBodyguard (JOI21_bodyguard)C++17
6 / 100
7937 ms1277680 KiB
#pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair < int, int > pii; typedef pair < ll, ll > pll; #define F first #define S second #define all(x) x.begin(), x.end() #define SZ(x) (int)x.size() #define Mp make_pair #define endl "\n" #define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define int ll const int M = 3e3 + 10; const int N = 6e3 + 10; const int N2 = 3e6 + 10; const int LOG = 20; const ll mod = 1e9 + 7; const ll inf = 4e9; typedef pair < ll , ll > Line; struct CHT{ set < pair < Line , ll > > S; set < pair < ll , Line > > I; ll INF = 4e18; inline void Add(Line X) { ll t = -INF; auto it = S.lower_bound({X, -INF}); while ((int)S.size()) { if (it == S.begin()) {t = -INF; break;} it --; ll r = Intersection(it->first, X); if (r <= it->second) I.erase({it->second, it->first}), it = S.erase(it); else {t = r; break;} } it = S.lower_bound({X, -INF}); while ((int)S.size()) { if (it == S.end()) break; ll r = Intersection(X, it->first); Line Y = it->first; I.erase({it->second, it->first}); it = S.erase(it); if (r <= t) { r = -INF; if (it != S.begin()) it --, r = Intersection(it->first, Y); S.insert({Y, r}); I.insert({r, Y}); return ; } if (it != S.end() && it->second <= r) continue; S.insert({Y, r}); I.insert({r, Y}); break; } S.insert({X, t}); I.insert({t, X}); } inline ll GetMax(ll X) { auto it = I.upper_bound({X, {INF, INF}}); it --; return (X * it->second.first + it->second.second); } inline ll Intersection(Line X, Line Y) { if (X.first == Y.first && X.second <= Y.second) return (-INF); if (X.first == Y.first) return (INF); return ((X.second - Y.second) / (Y.first - X.first)) + ((X.second - Y.second) % (Y.first - X.first) > 0); } }; CHT row[N], col[N]; int n, q, T[M], T2[M], fir[M], sec[M], C[M], dp[N][N], R[N][N], U[N][N], Qa[N2], Qb[N2], Ans[N2], EX[N2], EY[N2]; vector < int > cmx, cmy; vector < int > vec[N][N]; void Add(int a, int b) { cmx.push_back(a); cmy.push_back(b); } inline int lwrx(int a) { return lower_bound(all(cmx), a) - cmx.begin(); } inline int lwry(int a) { return lower_bound(all(cmy), a) - cmy.begin(); } signed main() { fast_io; cin >> n >> q; for(int i = 1; i <= n; i ++) { cin >> T[i] >> fir[i] >> sec[i] >> C[i]; T2[i] = T[i] + abs(fir[i] - sec[i]); C[i] /= 2; Add(T[i] + fir[i], T[i] - fir[i]); Add(T2[i] + sec[i], T2[i] - sec[i]); } Add(inf, inf); Add(-inf, -inf); sort(all(cmx)); sort(all(cmy)); cmx.resize(unique(all(cmx)) - cmx.begin()); cmy.resize(unique(all(cmy)) - cmy.begin()); for(int i = 1; i <= q; i ++) { cin >> Qa[i] >> Qb[i]; int a = lwrx(Qa[i] + Qb[i]), b = lwry(Qa[i] - Qb[i]); vec[a][b].push_back(i); EX[i] = cmx[a] - (Qa[i] + Qb[i]); EY[i] = cmy[b] - (Qa[i] - Qb[i]); } int sz1 = SZ(cmx), sz2 = SZ(cmy); for(int i = 1; i <= n; i ++) { pii A = Mp(T[i] + fir[i], T[i] - fir[i]), B = Mp(T2[i] + sec[i], T2[i] - sec[i]); A.F = lwrx(A.F); A.S = lwry(A.S); B.F = lwrx(B.F); B.S = lwry(B.S); if(A.F == B.F) /// going right { for(int j = A.S; j < B.S; j ++) { U[A.F][j] = max(U[A.F][j], C[i]); } } else /// going up { for(int j = A.F; j < B.F; j ++) { R[j][A.S] = max(R[j][A.S], C[i]); } } } /*for(int i = 0; i < N; i ++) { row[i].add(0, 0); col[i].add(0, 0); }*/ for(int i = sz1 - 1; i > 0; i --) { for(int j = sz2 - 1; j > 0; j --) { if(i + 1 < sz1 && j + 1 < sz2) { dp[i][j] = max(dp[i][j], dp[i + 1][j] + R[i][j] * (cmx[i + 1] - cmx[i])); dp[i][j] = max(dp[i][j], dp[i][j + 1] + U[i][j] * (cmy[j + 1] - cmy[j])); } col[i].Add({R[i - 1][j], dp[i][j]}); row[j].Add({U[i][j - 1], dp[i][j]}); for(auto id : vec[i][j]) { Ans[id] = max(row[j].GetMax(EY[id]), col[i].GetMax(EX[id])); } } } for(int i = 1; i <= q; i ++) { cout << Ans[i] << endl; } return 0; }
#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...