#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
int n,k,chf = 0;
cin>>n>>k;
unordered_set<int> s;
vector<int> v;
queue<int> q[n+1];
priority_queue<pair<int,int>> p;
for(int i=0;i<n;i++)
{
int temp;
cin>>temp;
v.push_back(temp);
q[temp].push(i);
}
for(int i=0;i<n;i++)
{
q[v[i]].pop();
if(s.find(v[i])==s.end())
{
chf++;
if(s.size()<k)
{
s.insert(v[i]);
if(q[v[i]].empty())
{
p.push(make_pair(INT_MAX,v[i]));
}
else
{
p.push(make_pair(q[v[i]].front(),v[i]));
}
}
else
{
//we have to replace a book
pair<int,int> pa = p.top();
p.pop();
s.erase(pa.second);
if(q[v[i]].empty())
{
p.push(make_pair(INT_MAX,v[i]));
}
else
{
p.push(make_pair(q[v[i]].front(),v[i]));
}
s.insert(v[i]);
}
}
}
cout<<chf;
return 0;
}
Sure. Your idea is correct, but your code isn't in the right order. Here's a general hint: do not duplicate code. You're doing the "if(q[v[i]].empty() ..." part to push into the priority_queue two times when it could be one, and it's not even in the right spot: you should always do that, even if you don't throw out a book, because you need to update the next index anyway.
That's the only observation, really. Here's the code rearranged and running ok: http://codeforces.com/contest/802/submission/27895579