We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Search
  4. Maximizing Mission Points
  5. Discussions

Maximizing Mission Points

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 19 Discussions, By:

recency

Please Login in order to post a comment

  • yashparihar729
    4 weeks ago+ 0 comments

    Here is my solution in java and C Click Here

    -1|
    Permalink
  • mineman1012221
    2 months ago+ 0 comments

    Here is the solution of Maximizing Mission Points Click Here

    0|
    Permalink
  • bhautik4avenger4
    11 months ago+ 1 comment

    https://zeroplusfour.com/maximizing-mission-points-hackerrank-solution/

    Here's how I did in all languages Java 8 , C++ , C , Python 3, Python 2.

    -1|
    Permalink
  • inanisumeet2019
    1 year ago+ 1 comment

    I used quadtree in c . I got timeout for testcase 8,9,10 . Is it slow if I compare 260 neighbours on an average for a point ?

    0|
    Permalink
  • willsonvieira
    2 years ago+ 4 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);
    }
    
    1|
    Permalink
    View more Comments..
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy