Submission #1247450

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247450		nqknht	Hotel (CEOI11_hot)	C++20	100 / 100	552 ms	37136 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);
#define TN "test"
    if (fopen(TN ".inp", "r"))
    {
        freopen(TN ".inp", "r", stdin);
        freopen(TN ".out", "w", stdout);
    }
    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;
    vector<ll> profit;
    for (int i = 1; i <= m; i++)
    {
        int id = lower_bound(a + 1, a + n + 1, make_pair(b[i].se, 0LL)) - a;
        if (id == n + 1)
            continue;
        id = get(1, 1, n, id, n);
        if (id == -1 || check[id] || a[id].se > b[i].fi)
            continue;
        check[id] = true;
        profit.push_back(b[i].fi - a[id].se);
        a[id].se = 100000000000000;
        update(1, 1, n, id);
    }
    sort(profit.begin(), profit.end(), greater<ll>());
    for (int i = 0; i < len(profit) && i < o; i++)
        mxprof += profit[i];
    cout << mxprof;
    return 0;
}

Compilation message (stderr)

hot.cpp: In function 'int main()':
hot.cpp:83:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         freopen(TN ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
hot.cpp:84:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         freopen(TN ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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