場に見えているカードの値をキーに、その山に含まれるカードの配列を値に持つ連想配列を考えます。

すなわち、例えば場に [3,2,1], [12,11], [7] という 3 つの山があるとき、
1 → [3,2,1]
11 → [12,11]
7 → [7]
と引けるような連想配列を用意します。この連想配列を適切に更新することで、問題を解くことができます。

例えば、上の例において、新たに 10 のカードを引いた場合、[12,11] の山の上に 10 のカードが置かれ、操作後の連想配列は次のような状態になっている必要があります。
1 → [3,2,1]
10 → [12,11,10]
7 → [7]
これは、

• 二分探索によりキー 11 を見つける
• キー 11 の持つ値 [12,11] を新たなキー 10 に割り当て直す
• キー 10 の持つ値 [12,11] の末尾に 10 を追加する

という手順により行うことができます。言語によっては、キーを割り当て直す際に配列のコピーが行われ、計算量が悪化することがあります。例えばC++であればmoveを用いることで、コピーを行うことなく参照を奪うことができます。(筆者はC++に詳しくないため、適切な説明は他のサイトに譲ります)

カード1枚を場に出す処理にかかる時間は、キーを見つける二分探索に \(O(\log N)\) 、その他は(ならし) \(O(1)\) であるため、\(N\) 枚合わせて \(O(N\log N)\) となります。カードを食べる部分に関する操作も全て合わせて \(O(N\log N)\) 時間で行えることが確かめられるので、全体の計算量も \(O(N\log N)\) となります。

実装例(C++)

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

int main(){
	int n,k;
	cin >> n >> k;
	vector<int>ans(n+1,-1);

	map<int,vector<int>>yama;
	for(int i=1;i<=n;i++){
		int x;
		cin >> x;
		auto it=yama.lower_bound(x);
		if(it!=yama.end()){
			yama[x]=move(it->second);
			yama.erase(it);
		}
		yama[x].push_back(x);
		if(yama[x].size()==k){
			for(auto y:yama[x])ans[y]=i;
			yama.erase(x);
		}
	}

	for(int i=1;i<=n;i++)cout << ans[i] << endl;
}

以下のPythonの実装例は、クエリあたり \(O(\sqrt{N})\) になるSortedSetを用いているため、計算量は\(O(N^{1.5})\) です。
実装例(Python)