HackerRank Cloudy Day problem solution

In this HackerRank Cloudy Day, problem-solution Complete the function maximum people which takes four arrays representing the populations of each town, locations of the towns, locations of the clouds, and the extents of coverage of the clouds respectively, and returns the maximum number of people that will be in a sunny town after removing exactly one cloud.

Problem solution in Python.

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the maximumPeople function below.
from collections import defaultdict


def maximumPeople(towns, cloud_start, cloud_end):
    towns = sorted(towns)
    cloud_start = sorted(cloud_start)
    cloud_end = sorted(cloud_end)

    cloud_start_i = 0
    cloud_end_i = 0
    clouds = set()

    d = defaultdict(int)
    free = 0
    for town_i in range(len(towns)):
        town_x = towns[town_i][0]
        while cloud_start_i < len(cloud_start) and cloud_start[cloud_start_i][0] <= town_x:
            clouds.add(cloud_start[cloud_start_i][1])
            cloud_start_i += 1
        while cloud_end_i < len(cloud_end) and cloud_end[cloud_end_i][0] < town_x:
            clouds.remove(cloud_end[cloud_end_i][1])
            cloud_end_i += 1
        if len(clouds) == 1:
            towns[town_i][2] = list(clouds)[0]
            d[list(clouds)[0]] += towns[town_i][1]
        elif len(clouds) == 0:
            free += towns[town_i][1]

    return max(d.values(), default=0) + free


def main():
    n = int(input().strip())
    p = [int(x) for x in input().strip().split()]
    x = [int(x) for x in input().strip().split()]
    towns = [[xi, pi, -1] for xi, pi in zip(x, p)]
    m = int(input().strip())
    y = [int(x) for x in input().strip().split()]
    r = [int(x) for x in input().strip().split()]
    cloud_start = [[y[i]-r[i], i] for i in range(m)]
    cloud_end = [[y[i]+r[i], i] for i in range(m)]
    result = maximumPeople(towns, cloud_start, cloud_end)
    print(result)

if __name__ == "__main__":
    main()

Problem solution in Java.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    static long maximumPeople(long[] p, long[] x, long[] y, long[] r) {
        long free = 0;
        long[] sum = new long[y.length];
        ArrayList<Event> al = new ArrayList<>();
        HashSet<Integer> clouds = new HashSet<>();
        for (int i = 0; i < p.length; i++) {
            al.add(new Event(1, x[i], p[i], i));
        }

        for (int i = 0; i < y.length; i++) {
            al.add(new Event(0, y[i] - r[i], -1, i));
            al.add(new Event(2, y[i] + r[i], -1, i));
        }

        Collections.sort(al);

        for (Event e : al) {
            if (e.type == 0) {
                clouds.add(e.index);
            } else if (e.type == 1) {
                if (clouds.isEmpty()) {
                    free += e.pr;
                } else {
                    if (clouds.size() == 1) {
                        for (int q : clouds) {
                            sum[q] += e.pr;
                        }
                    }
                }
            } else {
                clouds.remove(e.index);
            }
        }

        long mx = 0;
        for (long i : sum) {
            mx = Math.max(mx, i);
        }
        return free + mx;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long[] p = new long[n];
        for (int p_i = 0; p_i < n; p_i++) {
            p[p_i] = in.nextLong();
        }
        long[] x = new long[n];
        for (int x_i = 0; x_i < n; x_i++) {
            x[x_i] = in.nextLong();
        }
        int m = in.nextInt();
        long[] y = new long[m];
        for (int y_i = 0; y_i < m; y_i++) {
            y[y_i] = in.nextLong();
        }
        long[] r = new long[m];
        for (int r_i = 0; r_i < m; r_i++) {
            r[r_i] = in.nextLong();
        }
        long result = maximumPeople(p, x, y, r);
        System.out.println(result);
        in.close();
    }
}

class Event implements Comparable<Event> {
    int type;
    long x;
    long pr;
    int index;

    public Event(int type, long x, long pr, int index) {
        super();
        this.type = type;
        this.x = x;
        this.pr = pr;
        this.index = index;
    }

    @Override
    public int compareTo(Event e) {
        if (x != e.x) {
            return Long.compare(x, e.x);
        }
        return Integer.compare(type, e.type);
    }

}

Problem solution in C++.

#include <iostream>
#include <vector>
#include <utility>
#include <unordered_set>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 2e5;
const int MAXM = 1e5;
const int MAXP = 1e9;

vector<pair<int,int>> cities;
int y[MAXM];
int r[MAXM];

vector< pair<int,pair<int,int>> > endpoints;
ll prefsum[MAXN+1];
ll cover[MAXM];

ll people(int x1, int x2) {
    auto it1 = upper_bound(cities.begin(), cities.end(), make_pair(x1,0));
    auto it2 = upper_bound(cities.begin(), cities.end(), make_pair(x2,MAXP));
    if (it2 == cities.begin()) {
        return 0;
    }
    it2--;
    int i1 = it1-cities.begin();
    int i2 = it2-cities.begin();
    return max(0LL, prefsum[i2+1]-prefsum[i1]);
}

int main() {
    int n;
    cin >> n;
    cities.resize(n);

    ll sunny = 0;

    for (int i = 0; i < n; i++) {
        cin >> cities[i].second;
        sunny += cities[i].second;
    }
    for (int i = 0; i < n; i++) {
        cin >> cities[i].first;
    }

    sort(cities.begin(), cities.end());

    prefsum[0] = 0;
    for (int i = 0; i < cities.size(); i++) {
        prefsum[i+1] = prefsum[i]+cities[i].second;
    }

    int m;
    cin >> m;

    for (int i = 0; i < m; i++) {
        cin >> y[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> r[i];
        endpoints.push_back({y[i]-r[i], {0,i}});
        endpoints.push_back({y[i]+r[i], {1,i}});
    }

    sort(endpoints.begin(), endpoints.end());

    unordered_set<int> intervals;
    
    for (int i = 0; i < endpoints.size(); i++) {
        int toflag = endpoints[i].second.first; 
        int toind = endpoints[i].second.second;  
        if (i > 0) {
            int from = endpoints[i-1].first;
            int to = endpoints[i].first;
            int fromflag = endpoints[i-1].second.first; 

            if (fromflag == 1) {
                from++;
            }
            if (toflag == 0) {
                to--;
            } 
            if (intervals.size() == 1 && !(from == to && fromflag == 0 && toflag == 1)) {
                cover[*intervals.begin()] += people(from,to);
            }
            if (intervals.size() > 0) {
                sunny -= people(from,to);
            }
        }
        if (toflag == 0) {
            intervals.insert(toind);
        } else {
            intervals.erase(toind);
        }
    }

    ll ans = 0;

    for (int i = 0; i < m; i++) {
        ans = max(ans, cover[i]);
    }

    cout << sunny+ans << 'n';
}

Problem solution in C.

#include <stdio.h>
#include <stdlib.h>
typedef struct _node{
  int l;
  int r;
  long long zero;
  long long one;
  int off;
} node;
void build(int v,int tl,int tr);
void push(int v,int tl,int tr);
void range_update(int v,int tl,int tr,int pos1,int pos2);
long long sum(int v,int tl,int tr,int l,int r);
long long sum0(int v,int tl,int tr,int l,int r);
void sort_a2(int*a,int*b,int size);
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size);
int p[200000],l[200000],y[100000],r[100000];
node t[800000];

int main(){
  int n,m,i;
  long long max,temp;
  scanf("%d",&n);
  for(i=0;i<n;i++)
    scanf("%d",p+i);
  for(i=0;i<n;i++)
    scanf("%d",l+i);
  scanf("%d",&m);
  for(i=0;i<m;i++)
    scanf("%d",y+i);
  for(i=0;i<m;i++)
    scanf("%d",r+i);
  sort_a2(l,p,n);
  build(1,0,n-1);
  for(i=0;i<m;i++)
    range_update(1,0,n-1,y[i]-r[i],y[i]+r[i]);
  for(i=max=0;i<m;i++){
    temp=sum(1,0,n-1,y[i]-r[i],y[i]+r[i]);
    if(temp>max)
      max=temp;
  }
  printf("%lld",max+sum0(1,0,n-1,0,(1U<<31)-1));
  return 0;
}
void build(int v,int tl,int tr){
  int tm;
  if(tl==tr){
    t[v].l=t[v].r=l[tl];
    t[v].zero=p[tl];
    return;
  }
  tm=(tl+tr)/2;
  build(v*2,tl,tm);
  build(v*2+1,tm+1,tr);
  t[v].l=t[v*2].l;
  t[v].r=t[v*2+1].r;
  t[v].zero=t[v*2].zero+t[v*2+1].zero;
  return;
}
void push(int v,int tl,int tr){
  if(t[v].off==1){
    t[v].one=t[v].zero;
    t[v].zero=t[v].off=0;
    if(tl!=tr){
      t[v*2].off++;
      t[v*2+1].off++;
    }
  }
  else if(t[v].off>1){
    t[v].zero=t[v].one=t[v].off=0;
    if(tl!=tr){
      t[v*2].off+=2;
      t[v*2+1].off+=2;
    }
  }
  return;
}
void range_update(int v,int tl,int tr,int pos1,int pos2){
  int tm;
  if(pos2<t[v].l || pos1>t[v].r)
    return;
  push(v,tl,tr);
  if(pos1<=t[v].l && pos2>=t[v].r)
    t[v].off=1;
  else{
    tm=(tl+tr)/2;
    range_update(v*2,tl,tm,pos1,pos2);
    range_update(v*2+1,tm+1,tr,pos1,pos2);
    push(v*2,tl,tm);
    push(v*2+1,tm+1,tr);
    t[v].zero=t[v*2].zero+t[v*2+1].zero;
    t[v].one=t[v*2].one+t[v*2+1].one;
  }
  return;
}
long long sum(int v,int tl,int tr,int l,int r){
  int tm;
  if(r<t[v].l || l>t[v].r)
    return 0;
  push(v,tl,tr);
  tm=(tl+tr)/2;
  if(l<=t[v].l && r>=t[v].r)
    return t[v].one;
  else
    return sum(v*2,tl,tm,l,r)+sum(v*2+1,tm+1,tr,l,r);
}
long long sum0(int v,int tl,int tr,int l,int r){
  int tm;
  if(r<t[v].l || l>t[v].r)
    return 0;
  push(v,tl,tr);
  tm=(tl+tr)/2;
  if(l<=t[v].l && r>=t[v].r)
    return t[v].zero;
  else
    return sum0(v*2,tl,tm,l,r)+sum0(v*2+1,tm+1,tr,l,r);
}
void sort_a2(int*a,int*b,int size){
  if (size < 2)
    return;
  int m = (size+1)/2,i;
  int*left_a,*left_b,*right_a,*right_b;
  left_a=(int*)malloc(m*sizeof(int));
  right_a=(int*)malloc((size-m)*sizeof(int));
  left_b=(int*)malloc(m*sizeof(int));
  right_b=(int*)malloc((size-m)*sizeof(int));
  for(i=0;i<m;i++){
    left_a[i]=a[i];
    left_b[i]=b[i];
  }
  for(i=0;i<size-m;i++){
    right_a[i]=a[i+m];
    right_b[i]=b[i+m];
  }
  sort_a2(left_a,left_b,m);
  sort_a2(right_a,right_b,size-m);
  merge2(a,left_a,right_a,b,left_b,right_b,m,size-m);
  free(left_a);
  free(right_a);
  free(left_b);
  free(right_b);
  return;
}
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size){
  int i = 0, j = 0;
  while (i < left_size|| j < right_size) {
    if (i == left_size) {
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      j++;
    } else if (j == right_size) {
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      i++;
    } else if (left_a[i] <= right_a[j]) {
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      i++;
    } else {
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      j++;
    }
  }
  return;
}