Number Removal
Time limit: 1 s.
Memory limit: 256 MB
In a long hallway, there is a line of students represented by an array \(A\). Each student is holding a number.
A mischievous teacher comes in with a list of \(Q\) commands. Each command contains a number \(X\). Whenever the teacher calls out a number \(X\), the leftmost student holding that number quietly leaves the line. If no student is holding that number, nothing happens.
The teacher goes through all the commands one by one.
At the end, the remaining students stay in line, still in their original order.
Your task is to determine which students are left after all the teacher’s commands are completed.
Input
The first line contains two integers \(N\) and \(Q\). \((1 \le N, Q \le 2 \cdot 10^5)\)
The second line contains \(N\) integers \(A_1, A_2, ..., A_N\). \((1 \le A_i \le 10^9)\)
The third line contains \(Q\) integers \(X_1, X_2, ..., X_Q\). \((1 \le X_i \le 10^9)\)
Output
In a single print the remaining students in order from left to right.
Scoring
| Group | Constraints | Points |
|---|---|---|
| \(1\) | \(A_i = 1\) | \(21\) |
| \(2\) | \(1 \le N, Q \le 2 \cdot 10^3\) | \(17\) |
| \(3\) | \(X_i = 1\) | \(28\) |
| \(4\) | \(A_i \le 10^5\) | \(11\) |
| \(5\) | — | \(23\) |
Example
Input
7 4
2 5 4 2 1 3 4
5 9 4 2
Output
2 1 3 4
Note
For the sample [2, 5, 4, 2, 1, 3, 4] These are the operations step by step:
1. [2, 4, 2, 1, 3, 4] (remove 5)
2. [2, 4, 2, 1, 3, 4] (9 not present)
3. [2, 2, 1, 3, 4] (remove 4)
4. [2, 1, 3, 4] (remove 2)
Solution
For every value, store the indices where it occurs, in increasing order. On command \(X\), remove the first stored index for \(X\) if one exists. Mark that array position as removed.
Every index is inserted and removed at most once. With a hash map, the expected complexity is \(O(N+Q)\) time and \(O(N)\) memory.
#include <deque>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<long long> a(n);
unordered_map<long long, deque<int>> positions;
for (int i = 0; i < n; i++) {
cin >> a[i];
positions[a[i]].push_back(i);
}
vector<bool> removed(n, false);
while (q--) {
long long x;
cin >> x;
auto it = positions.find(x);
if (it != positions.end() && !it->second.empty()) {
removed[it->second.front()] = true;
it->second.pop_front();
}
}
for (int i = 0; i < n; i++) {
if (!removed[i]) {
cout << a[i] << ' ';
}
}
cout << '\n';
}