Official

B - Search and Delete Editorial by en_translator


Consider simulating the \(M\) operations sequentially.
The \(k\)-th operation can be, for example, simulated as follows.

Prepare an empty sequence \(A'=()\). For the \(k\)-th operation, prepare a flag \(F_k\) to manage whether an element removal has been already performed. Initially, \(F_k=\mathrm{False}\).
Perform the following procedure for \(i=1,2,\ldots,\lvert A\rvert\). Here, \(\lvert A\rvert\) is the length of \(A\) right before performing the \(k\)-th operation operation.

If \(A_i=B_k\) and \(F_k=\mathrm{False}\), set \(F_k\) to \(\mathrm{True}\), and do not insert \(A_j\) to the end of \(A'\). Otherwise, insert \(A_i\) to the end of \(A'\).

The resulting \(A'\) is the sought \(A\) after the procedure. By replacing \(A\) with \(A'\) and performing the same step for the next \(k\), the \(M\) operations can be simulated. Finally, print \(A\) after performing the operation \(M\) times according to the output format. Thus, the problem has been solved.
By the way, the time complexity of this solution is \(O(NM)\). This is fast enough under the constraints of this problem, but another solution allows processing even faster, for example in \(O(N+M\log \min(N,M))\).

Sample code in C++:

#include <bits/stdc++.h>
using namespace std;

int main(void){
	int n,m,x;
	bool flag;
	vector<int>a,nxt;

	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>x;
		a.push_back(x);
	}

	for(int i=0;i<m;i++){
		cin>>x;
		flag=true;
		n=a.size();
		nxt.clear();
		for(int j=0;j<n;j++){
			if((a[j]==x)&&flag)flag=false;
			else nxt.push_back(a[j]);
		}
		a=nxt;
	}

	n=a.size();
	for(int i=0;i<n;i++){
		cout<<a[i];
		if(i<(n-1))cout<<" ";
		else cout<<endl;
	}
	return 0;
}

posted:
last update: