Untitled

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;


//int range_to_next(int index, vector<int> *queue) { // передавать еще и максимальный range из уже присутствующих
//    if (index >= queue->size() - 1) return 600000;
//    int value = (*queue)[index];
//    int range = 600000;
//    for (int i = index + 1; i < queue->size(); ++i) {
//        if (value == (*queue)[i]) {
//            range = i - index;
//            break;
//        }
//    }
//    return range;
//}


int parent(int i) {
    return (i - 1) / 2;
}

int left(int i) {
    return 2 * i + 1;
}

int right(int i) {
    return 2 * i + 2;
}


void siftup(vector<pair<int, int>> * a, int i) {
    while (i > 0 && (*a)[parent(i)].second < (*a)[i].second) {
        swap((*a)[i], (*a)[parent(i)]);
        i = parent(i);
    }
}


void siftdown(vector<pair<int, int>> * a, int n, int i) {
    int j = i;
    while (true) {
        if (left(i) < n && (*a)[j].second < (*a)[left(i)].second) {
            j = left(i);
        }
        if (right(i) < n && (*a)[j].second < (*a)[right(i)].second) {
            j = right(i);
        }
        if (i == j) break;
        swap((*a)[i], (*a)[j]);
        i = j;
    }
}


void change_key(vector<pair<int, int>> *floor, int id, int new_key) {
    for (int i = 0; i < floor->size(); ++i) {
        if (id == (*floor)[i].first) {
            (*floor)[i].second = new_key;
            if (parent(i) >= 0 && new_key > (*floor)[parent(i)].second) {
                siftup(floor, i);
            } else if ((left(i) < floor->size() && new_key < (*floor)[left(i)].second) || (right(i) < floor->size() && new_key < (*floor)[right(i)].second)) {
                siftdown(floor, floor->size() - 1, i);
            }
            break;
        }
    }
}


int find_by_id(vector<pair<int, int>> * floor, int id) {
    int pos = -1;
    for (int i = 0; i < floor->size(); ++i) {
        if ((*floor)[i].first == id) {
            pos = i;
            break;
        }
    }
    return pos;
}


bool compare_keys(pair<int, int> k1, pair<int, int> k2) {
    return k1.second <= k2.second;
}


void decrease_all_keys(vector<pair<int, int>> * floor) {
    for (int i = 0; i < floor->size(); ++i) {
        (*floor)[i].second--;
    }
}



void make_stack_for_ids(vector<int> * queue, vector<stack<int>*> * cars_ids) {
    for (int i = queue->size() - 1; i >= 0; ++i) {
        int id = (*queue)[i] - 1;
        (*cars_ids)[id]->push(i);
    }
}


int get_range_to_next_opt(vector<stack<int>> * v, int id, int curr) {
    id--;
    if (!(*v)[id].empty()) {
        int next_pos = (*v)[id].top();
        int range = next_pos - curr;
        (*v)[id].pop();
        return range;
    } else {
        return 600000;
    }
}


int main() {
    int cars_count, floor_size, p;
    cin >> cars_count >> floor_size >> p;
    vector<pair<int, int>> floor(floor_size);
    vector<int> queue(p);

    int operations_count1 = 0;

    for (int i = 0; i < p; ++i) {
        cin >> queue[i];
    }

    vector<stack<int>> cars_indexes;

    for (int i = 0; i < floor_size; ++i) {
        floor[i] = pair<int, int>(-1, 600000 * 2);
    }

    for (int i = 0; i < p; ++i) {
        int curr = queue[i];
        if (find_by_id(&floor, curr) == -1) { // floor_size
            pop_heap(floor.begin(), floor.end(), compare_keys); // logN
            floor.pop_back(); // const
            floor.push_back(pair<int, int> (curr, get_range_to_next_opt(&cars_indexes, curr, i))); // (N) заменить на реализацию с map
            push_heap(floor.begin(), floor.end(), compare_keys); // logN
            operations_count1++; // const
        } else {
            change_key(&floor, curr, get_range_to_next_opt(&cars_indexes, curr, i)); // floor_size + (N)
        }
        decrease_all_keys(&floor); // floor_size
    }
    cout << operations_count1;
    return 0;
}