Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation

  • Height Queue

    You are given a queue of n people, where each person has a height represented by a positive integer. You need to process q queries, each of which is one of the following two types:
    1. Print Shorter People: Remove and print the heights of all people from the front of the queue whose height is less than or equal to a certain value d in the order they are popped.
    1. Add Person: Add a person to the end of the queue with height d.
    Write a program to process these queries efficiently.

    Input

    The first line of input contains two integers n and q, denoting the number of people in the initial queue and the number of queries, respectively (1 ≤ n, q ≤ 100 000).
    The second line contains n integers , where represents the height of the i-th person in the queue (1 ≤ ).
    Each of the next q lines represents a query of the form:
    • pop x if it is a query of type 1, where x is the maximum height allowed (1 ≤ x ≤ ).
    • add x if it is a query of type 2, where x is the height of the person to be added to the end of the queue (1 ≤ x ≤ ).

    Output

    For each query of type 1, output the heights of the popped people in the order they are popped, separated by spaces, on a separate line.
    Input
    Output
    5 6 5 3 8 7 10 pop 5 add 4 pop 9 add 9 pop 2 pop 11
    5 3 8 7 10 4 9

    Explanation

    The initial queue contains five people with heights 5, 3, 8, 7, and 10, in that order. The six queries are as follows:
    1. pop 5: The first two people in the queue have heights less than or equal to 5, so they are popped from the front of the queue and printed in order, resulting in the output "5 3".
    1. add 4: A person with height 4 is added to the end of the queue.
    1. pop 9: The first two people in the queue have heights less than or equal to 9, so they are popped from the front of the queue and printed in order, resulting in the output "8 7”.
    1. add 9: A person with height 9 is added to the end of the queue.
    1. pop 2: All people in the queue have heights greater than 2, so no one is popped from the front of the queue and printed. The output is an empty line.
    1. pop 11: All people in the queue have heights less than or equal to 11, so they are popped from the front of the queue and printed in order, resulting in the output "10 4 9".
     

    Constraints

    Time limit: 1.5 seconds

    Memory limit: 512 MB

    Output limit: 10 MB

    To check your solution you need to sign in
    Sign in to continue