fork download
copy 
  1. #include <iostream> 
  2. #include <unordered_map> 
  3. using namespace std; 
  4. class Node
  5. {
  6.     public: 
  7.         int data; 
  8.         Node* next=NULL; 
  9.         Node* prev=NULL;
  10. }; 
  11.  
  12. int main() 
  13. { 
  14.     Node* front = NULL; 
  15.     Node* rear = NULL;
  16. 	unordered_map<int, Node* > umap;
  17. 	int N,Q;
  18. 	cin >> N >> Q;
  19. 	for(int i=0; i < N; i++)
  20. 	{
  21. 	    int temp;
  22. 	    cin >> temp;
  23. 	    Node* fake = new Node();
  24. 	    fake->data = temp;
  25. 	    if(front == NULL && rear == NULL && umap.size() == 0)
  26. 	    {
  27. 	        front=fake;
  28. 	        rear=fake;
  29. 	    }
  30. 	    else
  31. 	    {
  32. 	        rear->next=fake;
  33. 	        fake->prev=rear;
  34. 	        rear=fake;
  35. 	    }
  36. 	    umap[temp]=fake;
  37. 	}
  38. 	for(int i=0; i < Q; i++)
  39. 	{
  40. 	    int ty;
  41. 	    cin >> ty;
  42. 	    if(ty == 3)
  43. 	    {
  44. 	        if(rear == NULL && front == NULL && umap.size() == 0)
  45. 	        {
  46. 	            cout<<"-1\n";
  47. 	        }
  48. 	        else
  49. 	        {
  50. 	            cout<<rear->data<<"\n";
  51. 	            umap.erase(rear->data);
  52. 	            if(rear == front)
  53. 	            {
  54. 	                rear = NULL;
  55. 	                front = NULL;
  56. 	            }
  57. 	            else
  58. 	            {
  59. 	                Node* fake=rear;
  60. 	                rear=rear->prev;
  61. 	                rear->next=NULL;
  62. 	                fake->prev=NULL;
  63. 	                 delete fake;
  64.  
  65. 	            }
  66. 	        }
  67. 	    }
  68. 	    else
  69. 	    {
  70. 	        int update;
  71. 	        cin>>update;
  72. 	        if(ty == 1)
  73. 	        {
  74.  
  75. 	            if(umap.find(update) == umap.end())
  76. 	            {
  77. 	                 Node* fake = new Node();
  78.     	             fake->data = update;
  79.     	             umap[update]=fake;
  80. 	                if(front == NULL && rear == NULL)
  81. 	                {
  82. 	                    front=fake;
  83. 	                    rear=fake;
  84. 	                }
  85. 	                else
  86. 	                {
  87.     	                 fake->next = front;
  88.     	                 front->prev = fake;
  89.     	                 front = fake;
  90. 	                }
  91. 	            }
  92. 	            else
  93. 	            {
  94. 	                cout<<"-1\n";
  95. 	            }
  96. 	        }
  97. 	        else
  98. 	        {
  99. 	             if(umap.find(update) == umap.end())
  100. 	             {
  101. 	                 cout<<"-1\n";
  102. 	             }
  103. 	             else
  104. 	             {
  105. 	                 Node* fake;
  106. 	                 fake = umap[update];
  107. 	                 if(front == rear)
  108. 	                 {
  109. 	                      rear = NULL;
  110. 	                      front = NULL;
  111. 	                 }
  112. 	                 else if(fake == front)
  113. 	                 {
  114. 	                     front=front->next;
  115. 	                     fake->next=NULL;
  116. 	                     front->prev=NULL;
  117. 	                 }
  118. 	                 else if(fake == rear)
  119. 	                 {
  120. 	                     rear=rear->prev;
  121. 	                     rear->next=NULL;
  122. 	                     fake->prev=NULL;
  123. 	                 }
  124. 	                 else
  125. 	                 {
  126. 	                     fake->prev->next = fake->next;
  127. 	                     fake->next->prev = fake->prev;
  128. 	                     fake->next = NULL;
  129. 	                     fake->prev = NULL;
  130. 	                 }
  131. 	                 delete fake;
  132. 	                 umap.erase(update);
  133. 	             }
  134. 	        }
  135. 	    }
  136. 	}
  137. }
Success #stdin #stdout 0s 4460KB
comments (?)
stdin
copy 
3 5
7 5 1
1 2
2 5
3
2 7
3
stdout
copy 
1
2
https://ideone.com/NRtSWG
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!