You are viewing a single comment's thread. Return to all comments →
//Pranet Verma #include <bits/stdc++.h> using namespace std; const int MAXN = 200000; const long long INF = 1e15; long long tree[MAXN * 4]; void makeTree() { for (int i = 1; i < MAXN * 4; ++i) { tree[i] = -INF; } } void update(int x, long long val, int u = 1, int l = 1, int r = MAXN) { if (l == r) { tree[u] = val; return; } int m = (l + r) / 2; if (x <= m) { update(x, val, 2 * u, l, m); } else { update(x, val, 2 * u + 1, m + 1, r); } tree[u] = max(tree[2 * u], tree[2 * u + 1]); } long long query(int x, int y, int u = 1, int l = 1, int r = MAXN) { if (x > r or y < l) { return -INF; } if (x <= l and r <= y) { return tree[u]; } int m = (l + r) / 2; return max(query(x, y, 2 * u, l, m), query(x, y, 2 * u + 1, m + 1, r)); } struct Point { int x, y, z, w; long long dp; bool operator < (const Point &o) const { return z < o.z; } }; Point p[MAXN + 1]; long long DP[MAXN + 1]; int X_LIM, Y_LIM; void merge(int l, int r) { int m = (l + r) / 2; vector<pair<int, int> > left; vector<pair<int, int> > right; for (int i = l; i <= m; ++i) { left.push_back({p[i].x, p[i].z}); } for (int i = m + 1; i <= r; ++i) { right.push_back({p[i].x, p[i].z}); } sort(left.begin(), left.end()); sort(right.begin(), right.end()); int left_l = 0; int left_r = -1; for (auto u : right) { int i = u.second; int x = u.first; while (left_r + 1 < left.size() and left[left_r + 1].first - x <= X_LIM) { ++left_r; int who = left[left_r].second; update(p[who].y, p[who].dp); } while (left_l < left.size() and x - left[left_l].first > X_LIM) { int who = left[left_l].second; update(p[who].y, -INF); ++left_l; } int yLow = max(1, p[i].y - Y_LIM); int yHigh = min(MAXN, p[i].y + Y_LIM); p[i].dp = max(p[i].dp, p[i].w + query(yLow, yHigh)); } while (left_l <= left_r) { int who = left[left_l].second; update(p[who].y, -INF); ++left_l; } } void solve(int l, int r) { if (l == r) { p[l].dp = max(p[l].dp, (long long)p[l].w); return; } int m = (l + r) / 2; solve(l, m); merge(l, r); solve(m + 1, r); } int main() { makeTree(); int n; scanf("%d %d %d", &n, &X_LIM, &Y_LIM); for (int i = 0; i < n; ++i) { scanf("%d %d %d %d", &p[i].x, &p[i].y, &p[i].z, &p[i].w); p[i].dp = -INF; } sort(p, p + n); for (int i = 0; i < n; ++i) { p[i].z = i; } solve(0, n - 1); long long ans = 0; for (int i = 0; i < n; ++i) { ans = max(ans, p[i].dp); } printf("%lld\n", ans); }
Seems like cookies are disabled on this browser, please enable them to open this website
Maximizing Mission Points
You are viewing a single comment's thread. Return to all comments →