Submission #1247383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247383		nqknht	Hotel (CEOI11_hot)	C++20	20 / 100	199 ms	32780 KiB

hot

#include <bits/stdc++.h>

#define ll long long
#define fi first
#define se second
#define len(s) (ll) s.size()

const ll I = 5e5 + 9;

using namespace std;

ll n, m, o;
pair<ll, ll> b[I], a[I], S[I * 4];
bool check[I];

void build(int x, int l, int r)
{
    if (l == r)
    {
        S[x].fi = a[l].se; // min money
        S[x].se = l;       // pos
        return;
    }
    int mid = (l + r) / 2;
    build(x * 2, l, mid);
    build(x * 2 + 1, mid + 1, r);
    int id;
    if (S[x * 2].fi < S[x * 2 + 1].fi)
        id = x * 2;
    else
        id = x * 2 + 1;
    S[x].fi = S[id].fi;
    S[x].se = S[id].se;
}

void update(int x, int l, int r, int pos)
{
    if (pos < l || pos > r || r < l)
        return;
    if (pos == l && pos == r)
    {
        S[x].fi = 1000000000000000;
        return;
    }
    int mid = (l + r) / 2;
    update(x * 2, l, mid, pos);
    update(x * 2 + 1, mid + 1, r, pos);
    int id;
    if (S[x * 2].fi < S[x * 2 + 1].fi)
        id = x * 2;
    else
        id = x * 2 + 1;
    S[x].fi = S[id].fi;
    S[x].se = S[id].se;
}

int get(int x, int l, int r, int L, int R)
{
    if (R < l || r < L || R < L || r < l)
        return -1;
    if (L <= l && r <= R)
        return S[x].se;
    int mid = (l + r) / 2;
    ll p = get(x * 2, l, mid, L, R);
    if (p == -1)
        p = get(x * 2 + 1, mid + 1, r, L, R);
    else
    {
        int np = get(x * 2 + 1, mid + 1, r, L, R);
        if(np != -1)
        if (a[p].se > a[np].se)
            p = np;
    }
    return p;
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> o;
    for (int i = 1; i <= n; i++)
        cin >> a[i].se >> a[i].fi; // money, lim
    sort(a + 1, a + n + 1);
    build(1, 1, n);
    for (int i = 1; i <= m; i++)
        cin >> b[i].fi >> b[i].se;
    sort(b + 1, b + m + 1, greater<pair<ll, ll>>());
    ll mxprof = 0;
    for (int i = 1, dem = 0; i <= m && dem < o; i++)
    {
        int id = lower_bound(a + 1, a + n + 1, make_pair(b[i].se, 0LL)) - a;
        // cout << i << " " << id << "\n";

        if (id == n + 1)
            continue;
        id = get(1, 1, n, id, n);
        if (check[id] || a[id].se > b[i].fi)
            continue;
        check[id] = true;
        dem++;
        mxprof += b[i].fi - a[id].se;
        a[id].se = 100000000000000;
        update(1, 1, n, id);
    }
    cout << mxprof;
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10