• + 0 comments

    Python3:

    from collections import defaultdict
        
        n = len(p)
        m = len(y)
        
        # Prepare events for cloud coverage
        cloud_start = []
        cloud_end = []
        for i in range(m):
            cloud_start.append((y[i] - r[i], i))
            cloud_end.append((y[i] + r[i], i))
        
        cloud_start.sort()
        cloud_end.sort()
        
        # Pair towns with their populations and sort by location
        towns = sorted([[x[i], p[i], -1] for i in range(n)], key=lambda t: t[0])
        
        active_clouds = set()
        cloud_start_i, cloud_end_i = 0, 0
        
        cloud_populations = defaultdict(int)
        free_population = 0
        
        for i in range(n):
            town_loc = towns[i][0]
            
            # Add clouds starting before or at town location
            while cloud_start_i < m and cloud_start[cloud_start_i][0] <= town_loc:
                active_clouds.add(cloud_start[cloud_start_i][1])
                cloud_start_i += 1
            
            # Remove clouds ending before town location
            while cloud_end_i < m and cloud_end[cloud_end_i][0] < town_loc:
                active_clouds.discard(cloud_end[cloud_end_i][1])
                cloud_end_i += 1
            
            if len(active_clouds) == 0:
                # Town is sunny
                free_population += towns[i][1]
            elif len(active_clouds) == 1:
                # Town covered by exactly one cloud
                c = next(iter(active_clouds))
                cloud_populations[c] += towns[i][1]
        
        # The maximum number of sunny people after removing one cloud
        max_cloud_pop = max(cloud_populations.values(), default=0)
        return free_population + max_cloud_pop