```python
def fill_template(template: str, values: dict) -> str:
    if not isinstance(template, str):
        raise ValueError("fill_template expects a string template")

    result: list[str] = []
    i: int = 0
    n: int = len(template)
    brace_depth: int = 0

    while i < n:
        ch: str = template[i]

        if ch == "{":
            # Check if this is a valid placeholder: must have a closing brace
            # and a non-empty name of only letters, digits, or underscores.
            if brace_depth == 0:
                # Standalone opening brace — literal
                result.append(ch)
                i += 1
                continue

            # Find the matching closing brace
            closing: int = -1
            for j in range(i + 1, n):
                if template[j] == "}":
                    closing = j
                    break

            if closing == -1:
                raise ValueError("unterminated placeholder")

            # Extract the name between the braces
            name_start: int = i + 1
            name_end: int = closing
            name: str = template[name_start:name_end]

            if not name:
                raise ValueError("empty placeholder name")

            for c in name:
                if not (c.isalnum() or c == "_"):
                    raise ValueError("placeholder name contains invalid character")

            if name not in values:
                raise ValueError(f"placeholder name '{name}' not found in values")

            result.append(values[name])
            i = closing + 1
            continue

        elif ch == "}":
            result.append(ch)
            i += 1
            continue

        else:
            result.append(ch)
            i += 1

    return "".join(result)
```

This implementation:
- Walks the template once with a single index variable
- Treats standalone `{` and `}` as literal characters
- Validates each placeholder: non-empty name, only alphanumeric/underscore characters, and present in the values dict
- Raises `ValueError` for any invalid placeholder (unterminated, empty name, invalid chars, unknown name)
- Raises `ValueError` for non-string template
- Uses a single pass with O(n) time and O(n) space for the result