leetcode-go/written-exam/ebay-2019-autumn/no2/main.cc

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <set>

using std::priority_queue; using std::set;

const int MAX = 100000;

int a[MAX];
int prev[MAX + 1];
int next[MAX + 1];

bool rem[MAX + 1];

struct node {
  int x;
  int y;
  node(int x, int y) : x(x), y(y) {}
  int operator<(const node &that) const {
    return that.y - this->y;
  }
};

int main() {
  int N, M, K;
  scanf("%d %d %d", &N, &M, &K);
  for (int i = 1; i <= N; i++) {
    prev[i] = K;
  }
  for (int i = 0; i < K; i++) {
    scanf("%d", &a[i]);
    next[i] = K;
    next[prev[a[i]]] = i;
    prev[a[i]] = i;
  }
  int m = 0, cnt = 0;
  memset(rem, 0, sizeof(rem));
  priority_queue<node> pq;
  for (int i = 0; i < K; i++) {
    if (rem[a[i]]) {
      pq.push(node(a[i], next[i]));
      continue; // Hit the cache
    }
    if (m == M) {
      m--;
      while (!pq.empty()) {
        node top = pq.top();
        pq.pop();
        if (rem[top.x]) {
          rem[top.x] = false;
          break;
        }
      }
    }
    m++;
    cnt++;
    rem[a[i]] = true;
    pq.push(node(a[i], next[i]));
  }
  printf("%d\n", cnt);
}