История изменений

типа, посчитать частичные суммы по координатам (нужны не все 10^9 координат, а только те, на которых лежит город или граница облака - всего 3*10^5 максимум):

1. P_0 население, не покрытое облаками

2. P_1 население, покрытое не более чем одним облаком

дальше перебрать все облака, и для каждого облака сложить P_0 слева от облака, плюс P_1 внутри облака плюс P_0 справа от облака; и выбрать облако с лучшим результатом

на все про все O(n log n) походу

и отдельно проработать случаи, когда город на границе облака

типа, посчитать частичные суммы по координатам:

1. P_0 население, не покрытое облаками

2. P_1 население, покрытое не более чем одним облаком

дальше перебрать все облака, и для каждого облака сложить P_0 слева от облака, плюс P_1 внутри облака плюс P_0 справа от облака; и выбрать облако с лучшим результатом

на все про все O(n log n) походу

и отдельно проработать случаи, когда город на границе облака

типа, посчитать частичные суммы по координатам:

1. P_0 население, не покрытое облаками

2. P_1 население, покрытое не более чем одним облаком

дальше перебрать все облака, и для каждого облака сложить P_0 слева от облака, плюс P_1 внутри облака плюс P_0 справа от облака; и выбрать облако с лучшим результатом

на все про все O(n log n) походу; хотя до этого еще сортировку по координатам надо провести

и отдельно проработать случаи, когда город на границе облака

типа, посчитать частичные суммы по координатам:

1. P_0 население, не покрытое облаками

2. P_1 население, покрытое не более чем одним облаком

дальше перебрать все облака, и для каждого облака сложить P_0 слева от облака, плюс P_1 внутри облака плюс P_0 справа от облака; и выбрать облако с лучшим результатом

на все про все O(n) походу; хотя до этого еще сортировку по координатам надо провести

и отдельно проработать случаи, когда город на границе облака