83092024-01-14 16:01:30anonTanúk (45 pont)cpp17Hibás válasz 34/45126ms24032 KiB
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define FastIO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;
typedef long long ll;
int main() {
    FastIO;
    bool flag;
    ll i, j, k, mh, N, H, K;
    cin >> N >> H >> K;
    set<ll> tsss;
    vector<array<ll, 2>> guests(N);
    for(i = 0; i < K; i++) {
        cin >> k;
        tsss.insert(k);
    }
    for(i = 0; i < N; i++)
        cin >> guests[i][0] >> guests[i][1];
    K = tsss.size();
    vector<ll> tss(K);
    i = 0;
    for(const auto &x : tsss)
        tss[i++] = x;
    vector<array<vector<ll>, 2>> eps(H + 1);
    for(i = 0; i < N; i++) {
        for(j = 0; j < 2; j++)
            eps[guests[i][j]][j].push_back(i);
    }
    unordered_set<ll> here;
    unordered_set<ll> lc;
    vector<ll> ans;
    j = 0;
    for(i = 1; i <= H; i++) {
        for(const auto &x : eps[i][0])
            here.insert(x);
        if(i == tss[j]) {
            if(ans.empty())
                lc = here;
            else {
                for(const auto &x : here) {
                    if(guests[ans.back()][1] < guests[x][0])
                        lc.insert(x);
                }
            }
            j++;
        }
        flag = !lc.empty();
        if(flag) {
            flag = false;
            for(const auto &x : eps[i][1]) {
                if(lc.find(x) != lc.end()) {
                    flag = true;
                    break;
                }
            }
        }
        if(flag) {
            mh = *(here.begin());
            for(const auto &x : here) {
                if(guests[mh][1] < guests[x][1])
                    mh = x;
            }
            ans.push_back(mh);
            j = upper_bound(all(tss), guests[mh][1]) - tss.begin();
            lc.clear();
        }
        for(const auto &x : eps[i][1])
            here.erase(x);
    }
    cout << ans.size() << '\n';
    for(const auto &x : ans)
        cout << x + 1 << ' ';
    cout << '\n';
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base34/45
1Elfogadva0/03ms1832 KiB
2Hibás válasz0/034ms12480 KiB
3Elfogadva2/234ms12692 KiB
4Elfogadva2/23ms3252 KiB
5Elfogadva2/23ms2848 KiB
6Részben helyes1/23ms3476 KiB
7Hibás válasz0/23ms3564 KiB
8Részben helyes1/23ms3556 KiB
9Elfogadva2/24ms7516 KiB
10Hibás válasz0/24ms4800 KiB
11Hibás válasz0/26ms8008 KiB
12Elfogadva2/27ms8264 KiB
13Elfogadva2/28ms8668 KiB
14Elfogadva2/28ms6136 KiB
15Elfogadva2/29ms6756 KiB
16Részben helyes1/210ms9400 KiB
17Hibás válasz0/250ms17228 KiB
18Elfogadva2/268ms17976 KiB
19Elfogadva2/275ms16904 KiB
20Elfogadva2/283ms17108 KiB
21Elfogadva2/270ms19260 KiB
22Elfogadva2/290ms21588 KiB
23Elfogadva2/278ms21676 KiB
24Elfogadva3/3126ms24032 KiB