fork download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<fstream>
  7. #include<map>
  8. #include<ctime>
  9. #include<set>
  10. #include<queue>
  11. #include<cmath>
  12. #include<vector>
  13. #include<bitset>
  14. #include<functional>
  15. #define x first
  16. #define y second
  17. #define mp make_pair
  18. #define pb push_back
  19. #define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
  20. #define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
  21. using namespace std;
  22.  
  23. typedef long long LL;
  24. typedef double ld;
  25.  
  26. const int MAX=1000000+10;
  27.  
  28. int n,k,p;
  29. int want[MAX];
  30. int begin[MAX],next[MAX];
  31.  
  32. int main()
  33. {
  34. //	freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
  35. 	int i;
  36. 	cin>>n>>k>>p;
  37. 	REP(i,1,p)
  38. 		scanf("%d",&want[i]);
  39. 	REP(i,1,n)
  40. 		begin[i]=p+1;
  41. 	for(i=p;i>=1;--i)
  42. 	{
  43. 		next[i]=begin[ want[i] ];
  44. 		begin[want[i]]=i;
  45. 	}
  46. 	set< pair<int,int> > toDel;
  47. 	int ans=0;
  48. 	REP(i,1,p)
  49. 	{
  50. 		int u=want[i];
  51. 		set< pair<int,int> >::iterator it=toDel.find( mp( -begin[u],u ) );
  52. 		if(it==toDel.end())
  53. 		{
  54. 			++ans;
  55. 			if((int)toDel.size()==k)
  56. 				toDel.erase(toDel.begin());
  57. 			begin[u]=next[begin[u]];
  58. 			toDel.insert( mp(-begin[u],u) );
  59.  
  60. 		}
  61. 		else
  62. 		{
  63. 			toDel.erase(mp(-begin[u],u));
  64. 			begin[u]=next[begin[u]];
  65. 			toDel.insert(mp(-begin[u],u));
  66. 		}
  67. 	}
  68. 	cout<<ans<<endl;
  69. 	return 0;
  70. }
  71.  
Success #stdin #stdout 0s 15064KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/NvzwLG
language:
C++ (gcc 8.3)
created:
10 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!