ECJAN20D - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Enchoding January’20

Author: Akash Kumar Bhagat
Tester: Soham Chakrabarti
Editorialist: Akash Kumar Bhagat

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

STACK,HASHING

PROBLEM:

You are provided with a stack of N numbers (may or may not be distinct) and you have to perform q queries on the stack.
There are 2 types of Query to be performed

i) 1 L s1 s2 … sL To add the stack of L numbers (s1,s2 … sL) to the stack, with sL on the top
ii) 2 R To Remove R numbers from the top of the stack
And at any moment, the numbers in the stack should be unique. If there are duplicates, then remove the duplicate from the top side.
After the query execution, you are needed to print the stack content from top to bottom.

EXPLANATION:

One has to maintain a stack, and a hash map(to test the uniqueness of the stack element). After taking the input of the stack
status in an array, push those numbers in the stack while checking(if the element is marked True or not) and update the Hash map(as True).

After this one can start reading the queries. For each query, the First letter decides the query type.

If the query type is 1, take the input L and the sequence s1,s2…sL and push the sequence to the stack while checking and updating
the Hash map as done in the beginning.
If the query type is 2, then pop R elements from the stack one by one while updating the Hash map(as False)
After the query execution, pop the stack and display the poped elements. :slight_smile:

SOLUTIONS:

Setter’s Solution

2 Likes
2

int main() {
// your code goes here

int t;
cin >> t;

while(t-- > 0){
    int n, q;
    cin >> n >> q;
    stack<int> st;
    
    int count[100001];
    
    
    
    for(int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if(count[x]!=1){
            st.push(x);
            count[x] = 1;
        }
    }
    
    for(int i = 0; i < q; i++) {
        int a;
        cin >> a;
        
        if(a == 1) {
            
            int l;
            cin >> l;
            
            for(int j = 0; j < l; j++) {
                int x;
                cin >> x;
                if(count[x] != 1)
                {
                    st.push(x);
                    count[x] = 1;
                }
            }
            
        }else {
            int r;
            cin >> r;
            for(int j = 0; j < r; j++){
                if(!st.empty()){
                    count[st.top()] = 0;
                    st.pop();
                }else{
                    break;
                }
            }
        }
    }
    
    while(!st.empty()) {
        cout << st.top() << " ";
        st.pop();
    }
    
    cout << "" << endl;
    
}





return 0;

}`

its my code i use array for checking duplicates but still its not working