FastPrep
Problem · Segment Tree

Dynamic Wall Building and Range Query

Learn this problem
● MediumCapital One logoCapital OneFULLTIMEOA

Problem statement

Complete the function below. The function receives the full standard input as a single string and must return the exact standard output lines for the described problem.

Maintain a 1D line of length n with indices 0..n-1, initially with no walls. You are given a sequence of operations of two types:

  • build i: build a wall at index i (idempotent).
  • query l r: check whether there exists at least one wall in the inclusive range [l, r].

For each query operation, output 1 if the range contains at least one wall, otherwise 0.

Input Format (stdin):

  • Line 1: Integer n, the length of the wall line.
  • Line 2: Integer q, the number of operations.
  • Next q lines: Each line is either build i or query l r.

Output Format: Return the query results as an array of lines, one result per query operation, in order. Each result is either 0 or 1.

Function

solveOneDynamicWallRangeQuery(input: String) → String[]

Examples

Example 1

input = "5\n1\nquery 0 4"return = ["0"]
Input stdin: '5\n1\nquery 0 4'. Line 1: n=5. Line 2: 1 operation. Line 3: 'query 0 4'. No walls have been built, so the range [0,4] contains no wall. Output is ["0"].

Constraints

  • 1 <= n <= 2 * 105
  • 1 <= q <= 2 * 105 (number of operations)
  • All indices i, l, r satisfy 0 <= l <= r <= n - 1
  • Each operation is either build i or query l r

More Capital One problems

drafts saved locally
public String[] solveOneDynamicWallRangeQuery(String input) {
    // write your code here
}
input"5\n1\nquery 0 4"
expected["0"]
checking account