CF 1184B1 - The Doctor Meets Vader (Easy)

Rating: 1400
Tags: binary search, sortings
Solve time: 5m 28s
Verified: yes

Solution

Problem Understanding

Each spaceship has an attack power. Each empire base has a defense value and a gold amount.

A spaceship can destroy every base whose defense is not greater than the spaceship's attack power. Since destroying a base gives all of its gold, the answer for a spaceship is simply the sum of gold over all bases with defense less than or equal to its attack power.

The task is to compute this value for every spaceship, preserving the original spaceship order.

The constraints are large enough to rule out straightforward simulation. There can be up to $10^5$ spaceships and $10^5$ bases. Checking every base for every spaceship would require $10^{10}$ comparisons in the worst case, which is far beyond what can run within a few seconds.

The structure of the problem is very favorable for sorting. Whether a base contributes to a spaceship depends only on the comparison

$$d \le a$$

where $d$ is the base defense and $a$ is the spaceship attack power. Once the bases are sorted by defense, all eligible bases for a given spaceship form a prefix of that sorted order. Prefix queries suggest prefix sums and binary search.

Several edge cases deserve attention.

Consider multiple bases with the same defense:

The correct answer is:

A careless binary search that finds only one occurrence of defense 5 would miss some gold. We must find the position after the last defense value less than or equal to the attack power.

Consider a spaceship that cannot defeat any base:

The correct answer is:

The binary search must correctly return an empty prefix.

Consider a spaceship stronger than every base:

The correct answer is:

The search should return the entire prefix sum rather than running past the array bounds.

Another subtle case is defense value 0:

The answers are:

5 12

Bases with defense 0 are attackable even by a spaceship with attack power 0.

Approaches

The most direct solution is brute force. For each spaceship, iterate through all bases. Whenever a base has defense at most the spaceship's attack power, add its gold to the total.

This is correct because it checks exactly the condition from the statement. Unfortunately, with $10^5$ spaceships and $10^5$ bases, it performs $10^{10}$ checks. Even a tiny fraction of that would already be too slow.

The key observation is that only the defense values matter when deciding whether a base contributes. If we sort all bases by defense, then for any attack power $a$, every attackable base appears in a contiguous prefix of the sorted list.

For example, after sorting defenses:

Defense: 0 2 4 9
Gold:    1 8 2 4

A spaceship with attack power 5 can defeat exactly the first three bases. The problem becomes:

"How much gold is contained in the prefix ending at the last defense value not exceeding 5?"

Prefix sums answer the second question instantly, while binary search answers the first.

We sort the bases by defense, build a prefix-sum array of gold, and for each spaceship use binary search to locate the first defense greater than its attack power. Everything before that position contributes to the answer.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(s·b)	O(1)	Too slow
Optimal	O(b log b + s log b)	O(b)	Accepted

Algorithm Walkthrough

Read all spaceship attack powers.
Read all bases as pairs (defense, gold).
Sort the bases by defense value.

After sorting, every spaceship's valid bases form a prefix of the array. 4. Create an array containing only the sorted defenses. 5. Build a prefix-sum array of gold.

Let pref[i] store the total gold in the first i bases of the sorted order. Using a length b + 1 prefix array makes empty-prefix handling simple. 6. For each spaceship attack power a, perform binary search on the sorted defense array.

Find the first position whose defense is greater than a. In Python this is bisect_right. 7. If the returned position is pos, then exactly the first pos bases are attackable.

The answer is pref[pos]. 8. Output all answers in the original spaceship order.

Why it works

After sorting by defense, every base with defense at most a appears before every base with defense greater than a. Binary search finds the boundary between these two groups.

The returned position pos is exactly the number of attackable bases. Since pref[pos] stores the total gold contained in the first pos sorted bases, it equals the sum of gold from every base that the spaceship can destroy. This argument holds independently for every spaceship, so all reported answers are correct.

Python Solution

import sys
from bisect import bisect_right

input = sys.stdin.readline

def solve():
    s, b = map(int, input().split())
    attacks = list(map(int, input().split()))

    bases = []
    for _ in range(b):
        d, g = map(int, input().split())
        bases.append((d, g))

    bases.sort()

    defenses = [d for d, _ in bases]

    pref = [0] * (b + 1)
    for i in range(b):
        pref[i + 1] = pref[i] + bases[i][1]

    ans = []
    for a in attacks:
        pos = bisect_right(defenses, a)
        ans.append(str(pref[pos]))

    print(" ".join(ans))

if __name__ == "__main__":
    solve()

The sorted bases array establishes the ordering needed for binary search. The defenses array is extracted because bisect_right operates on a single sorted list.

The prefix-sum array has length b + 1. The extra leading zero removes special cases. If no base can be attacked, bisect_right returns 0 and pref[0] is already the correct answer.

Using bisect_right instead of bisect_left is crucial. We need all bases with defense less than or equal to the attack power. bisect_right returns the first position after the last equal element, which includes every valid base.

Python integers automatically handle the maximum possible gold totals. Even in the largest test, the sum fits comfortably.

Worked Examples

Sample 1

Input:

Sorted bases:

Index	Defense	Gold	Prefix Gold
0	0	1	1
1	2	8	9
2	4	2	11
3	9	4	15

Queries:

Attack	bisect_right Position	Answer
1	1	1
3	2	9
5	3	11
2	2	9
4	3	11

Output:

1 9 11 9 11

This trace shows the central idea of the solution. Every query becomes a search for a boundary in the sorted defense array, followed by a prefix-sum lookup.

Custom Example

Input:

Sorted bases:

Index	Defense	Gold	Prefix Gold
0	2	1	1
1	5	2	3
2	5	3	6
3	8	7	13

Queries:

Attack	bisect_right Position	Answer
5	3	6
4	1	1
10	4	13

Output:

6 1 13

This example demonstrates why bisect_right is needed. Attack power 5 must include both bases whose defense is exactly 5.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(b log b + s log b)	Sorting bases costs O(b log b), each spaceship performs one binary search
Space	O(b)	Sorted arrays and prefix sums

With $b,s \le 10^5$, sorting about $10^5$ elements and performing $10^5$ binary searches is easily fast enough. Memory usage is linear in the number of bases and comfortably fits within the limit.

Test Cases

# helper: run solution on input string, return output string
import sys
import io
from bisect import bisect_right

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)

    input = sys.stdin.readline

    s, b = map(int, input().split())
    attacks = list(map(int, input().split()))

    bases = []
    for _ in range(b):
        d, g = map(int, input().split())
        bases.append((d, g))

    bases.sort()

    defenses = [d for d, _ in bases]

    pref = [0]
    for _, g in bases:
        pref.append(pref[-1] + g)

    ans = []
    for a in attacks:
        pos = bisect_right(defenses, a)
        ans.append(str(pref[pos]))

    return " ".join(ans)

# provided sample
assert run(
"""5 4
1 3 5 2 4
0 1
4 2
2 8
9 4
"""
) == "1 9 11 9 11", "sample 1"

# minimum size
assert run(
"""1 1
0
0 5
"""
) == "5", "minimum case"

# no attackable bases
assert run(
"""2 2
0 1
2 5
3 7
"""
) == "0 0", "empty prefix"

# all equal defenses
assert run(
"""3 3
4 5 6
5 1
5 2
5 3
"""
) == "0 6 6", "equal defenses"

# boundary condition with duplicates
assert run(
"""1 4
5
2 1
5 2
5 3
8 7
"""
) == "6", "must include all defense=5 bases"

Test input	Expected output	What it validates
One spaceship, one base, both 0	5	Minimum constraints
Attack powers below every defense	0 0	Empty-prefix handling
Multiple equal defenses	0 6 6	Correct treatment of duplicates
Attack power exactly matching duplicate defenses	6	Requires `bisect_right` rather than `bisect_left`

Edge Cases

Consider a spaceship that cannot defeat any base:

Sorted defenses are [2, 3]. bisect_right([2, 3], 1) returns 0. The algorithm outputs pref[0] = 0, which is correct because no base satisfies d ≤ 1.

Consider several bases with the same defense:

After sorting, defenses are [5, 5, 5]. bisect_right(..., 5) returns 3, not 1. The answer becomes pref[3] = 9, correctly including every base whose defense equals the attack power.

Consider a spaceship stronger than every base:

bisect_right([1, 5, 10], 100) returns 3, which equals the number of bases. The algorithm uses pref[3] = 9, the sum of all gold.

Consider defense value zero:

The sorted defenses are [0, 1]. For attack power 0, the binary search returns 1, so the answer is pref[1] = 5. For attack power 1, it returns 2, producing 12. Both outputs match the intended behavior exactly.