String insertion P21174


Statement
 

pdf   zip

html

Implement an efficient data structure to keep a dynamic array A[0..] of strings, with two operations:

  • Is i: Increase the size of A by one (like A.push_back("");). Move every string at a position j such that ji one position to its right. Store the string s at the i-th position, which now is empty.
  • Cj: Print the j-th character (0 based) of the whole array, considering the concatenation of all its strings from left to right.

Input

Input consists of just one case. Assume that each s has between 1 and 10 lowercase letters, each i is between 0 and the current number of strings, and each j is between 0 and the current number of characters minus one. The total number of operations is at most 3 · 105. An ‘E’ marks the end of the input.

Output

Print a line with the letter at the j-th position for each ‘C’ operation.

Public test cases
  • Input

    I hello 0
    C 0
    C 4
    I bye 0
    C 0
    C 7
    I hi 1
    C 4
    C 1
    C 9
    E
    

    Output

    hoboiyo
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Quinzè Concurs de Programació de la UPC - Semifinal
    Date
    2017-06-29