8327 2024. 01. 14 18:15:45 zsombor Tanúk (45 pont) cpp17 Elfogadva 45/45 133ms 9996 KiB
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, h, k, done = 0, nxt = 0, mxi = 0;
vector <int> t;
vector <int> l(1e5 + 1, 0);
vector <int> r(1e5 + 1, 0);
vector <pair <int, int>> s1;
vector <pair <int, int>> s2;
vector <int> ans;

int main()
{
    cin >> n >> h >> k;
    t.resize(k);
    for (int& i : t) cin >> i;
    sort(t.begin(), t.end());
    t.push_back(1e9);
    for (int i = 1; i <= n; i++) {
        cin >> l[i] >> r[i];
        int lb = lower_bound(t.begin(), t.end(), l[i]) - t.begin();
        if (t[lb] > r[i]) continue;
        s1.push_back({ r[i],i });
        s2.push_back({ l[i], i });
    }
    sort(s1.begin(), s1.end());
    sort(s2.begin(), s2.end());
    for (auto p : s1) {
        int i = p.second;
        if (done >= l[i]) continue;
        while (nxt < s2.size()) {
            int j = s2[nxt].second;
            if (l[j] > r[i]) break;
            if (r[j] > r[mxi]) mxi = j;
            nxt++;
        }
        done = r[mxi];
        ans.push_back(mxi);
    }
    cout << ans.size() << "\n";
    for (int i : ans) cout << i << " ";
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 45/45
1 Elfogadva 0/0 3ms 3164 KiB
2 Elfogadva 0/0 46ms 4668 KiB
3 Elfogadva 2/2 37ms 3696 KiB
4 Elfogadva 2/2 3ms 3780 KiB
5 Elfogadva 2/2 4ms 4116 KiB
6 Elfogadva 2/2 3ms 4076 KiB
7 Elfogadva 2/2 4ms 4328 KiB
8 Elfogadva 2/2 4ms 4544 KiB
9 Elfogadva 2/2 4ms 4504 KiB
10 Elfogadva 2/2 4ms 4508 KiB
11 Elfogadva 2/2 4ms 4944 KiB
12 Elfogadva 2/2 7ms 4996 KiB
13 Elfogadva 2/2 8ms 4996 KiB
14 Elfogadva 2/2 9ms 5036 KiB
15 Elfogadva 2/2 13ms 5560 KiB
16 Elfogadva 2/2 13ms 5588 KiB
17 Elfogadva 2/2 68ms 7580 KiB
18 Elfogadva 2/2 112ms 8864 KiB
19 Elfogadva 2/2 116ms 9076 KiB
20 Elfogadva 2/2 118ms 9008 KiB
21 Elfogadva 2/2 112ms 8880 KiB
22 Elfogadva 2/2 123ms 9312 KiB
23 Elfogadva 2/2 123ms 9524 KiB
24 Elfogadva 3/3 133ms 9996 KiB