FastPrep
Problem · Array

Find ID of Soldier

● EasyHSBCOA

There are N soldiers standing in a line, with IDs from 1 to N, in ascending order. They are participating in an exercise consisting of Q actions. During the ith action, the Major calls S numbers row and col. The soldiers at the rowith and (coli)th positions swap places, and so on until (rowi+m < (coli - m). Each of the soldier's IDs will be covered in the range [rowi, coli] for at most one action.

Write an algorithm to find the ID of the soldier at Kth position in the line after all the actions are completed.

Input

  • The first line of the input consists of an integer- num, representing the number of soldiers (N).
  • The second line consists of two space-separated integers- actions and numSoldiers, representing the number of actions (Q) and number of soldiers called by the Major (S), respectively.
  • The next Q lines consist of S space-separated integers- rowi and coli, representing the positions of the soldiers initially called for the ith action.
  • The last line consists of an integer- posSoldier, representing the position of the soldier whose ID is requested to be found after Q actions (K).

    • Output

    Print an integer representing the ID of the Kth position soldier in the line after Q actions.

    Constraints

    1 ≤ posSoldier ≤ num ≤ 10^5
    1 ≤ actions ≤ 10^5
    1 ≤ rowi, coli ≤ num
    1 ≤ i ≤ actions

    Examples
    01 · Example 1
    num = 10
actions = 2
numSoldiers = 2
swaps = [[1, 5], [6, 10]]
posSoldier = 1
return = 5
    Step1: After the 1st action, the position of soldiers is in the order: 5 4 3 2 1 6 7 8 9 10.
    Step2: After the 2nd action, the position of soldiers is in the order: 5 4 3 2 1 10 9 8 7 6.
    Step3: The ID of the soldier at position 1 is 5.
    So, the output is 5.
    Constraints
    🐝
    More HSBC problems
    drafts saved locally
    public int findIdOfSoldier(int num, int actions, int numSoldiers, int[][] swaps, int posSoldier) {
  // write your code here
}
    num10
    actions2
    numSoldiers2
    swaps[[1, 5], [6, 10]]
    posSoldier1
    expected5
    sign in to submit