fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. int n,k,arr[250000],ne[250000],ans[250000],t[250000];
  5. set<int>se;
  6. signed main(){
  7. 	cin>>n>>k;
  8. 	for(int i=1;i<=n;i++){
  9. 		cin>>arr[i];
  10. 		ne[i]=-1;
  11. 		t[i]=1;
  12. 	}
  13. 	for(int i=1;i<=n;i++){
  14. 		auto it=se.lower_bound(arr[i]);
  15. 		if(it==se.end()){
  16. 			se.insert(arr[i]);
  17. 			if(t[arr[i]]==k){
  18. 				for(int j=arr[i];j!=-1;j=ne[j]){
  19. 					ans[j]=i;
  20. 				}
  21. 				se.erase(arr[i]);
  22. 			}
  23. 		}else{
  24. 			int pos=*it;
  25. 			se.erase(pos);
  26. 			t[arr[i]]=t[pos]+1;
  27. 			ne[arr[i]]=pos;
  28. 			if(t[arr[i]]==k){
  29. 				for(int j=arr[i];j!=-1;j=ne[j]){
  30. 					ans[j]=i;
  31. 				}
  32. 				se.erase(arr[i]);
  33. 			}
  34. 		}
  35. 	}
  36. 	for(int i=1;i<=n;i++){
  37. 		if(ans[i]==0){
  38. 			cout<<-1<<"\n";
  39. 			continue;
  40. 		} 
  41. 		cout<<ans[i]<<"\n";
  42. 	}
  43. }
Success #stdin #stdout 0.01s 7624KB
comments (?)
stdin
copy 
5 2
3 5 2 1 4
stdout
copy 
4
3
3
-1
4
https://ideone.com/irMEgF
language:
C++ (gcc 8.3)
created:
4 days ago
visibility:
public

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!