CSES 1084 – Apartments

We match applicants with apartments. Each applicant can take an apartment within ±k of his desired size.

// https://cses.fi/problemset/task/1084/
int n, m, k; 
cin >> n >> m >> k;

vector<int> s(n);
for (int i = 0; i < n; i++) cin >> s[i];
sort(s.begin(), s.end());

multiset<int> ms;
while (m--) {
    int x; cin >> x;
    ms.insert(x);
}

int ans = 0;
for (int i = 0; i < n; i++) {
    int l = s[i] - k, r = s[i] + k;
    auto it = ms.lower_bound(l);   // first apt >= l
    if (it != ms.end() && *it <= r) {
        ans++;
        ms.erase(it); 
    }
}
cout << ans << "\n";

CSES 1091 – Concert Tickets

Each customer wants a ticket with price ≤ x.

// https://cses.fi/problemset/task/1091/
int n, m; 
cin >> n >> m;

multiset<int> ms;
for (int i = 0; i < n; i++) {
    int x; cin >> x;
    ms.insert(x);
}

for (int i = 0; i < m; i++) {
    int a; cin >> a;
    auto it = ms.upper_bound(a); // first element > a
    if (it != ms.begin()) {
        --it;                   
        cout << *it << "\n";
        ms.erase(it);
    } else {
        cout << -1 << "\n";
    }
}

Codeforces 637B – Chat Order

We need to print the chat names in the order of their last appearance.

// https://codeforces.me/problemset/problem/637/B
int n; cin >> n;
vector<string> x(n);
map<string, char> m;

for (int i = 0; i < n; i++) {
    cin >> x[i];
    m[x[i]] = 'n';
}

for (int i = n - 1; i >= 0; i--) {
    if (m[x[i]] == 'n') {
        cout << x[i] << "\n";
        m[x[i]] = 'y';
    }
}

These three problems cover:

• lower_bound and upper_bound on multisets
• Erasing elements safely
• Using map to track visits and preserve last appearance

Notes

1. Use vector<pair<int,int>> instead of map to keep all intervals (map removes duplicates and sorts only by key).
2. Sort intervals by end time using a lambda comparator:

cpp sort(v.begin(), v.end(), [](auto &x, auto &y){ return x.second < y.second; }); ---