nik96's blog

By nik96, history, 2 months ago, In English,
#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;
}
 
 
 
 
  • Vote: I like it  
  • -8
  • Vote: I do not like it  

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by nik96 (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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