Submission #466441

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
466441	2021-08-19T09:46:13 Z	Lam_lai_cuoc_doi	Hotel (CEOI11_hot)	C++17	100 / 100	908 ms	22492 KB

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T>
void read(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

constexpr bool typetest = 0;
constexpr int N = 5e5 + 5;
constexpr int Inf = 1e9 + 7;
int n, m, k;

struct SegmentTree
{
    int st[N * 4], a[N], n;
    SegmentTree()
    {
        fill_n(a, N, Inf);
    }
    void Build(int id, int l, int r)
    {
        if (l > r)
            return;
        if (l == r)
        {
            st[id] = l;
            return;
        }
        Build(id << 1, l, (l + r) / 2);
        Build(id << 1 | 1, (l + r) / 2 + 1, r);
        st[id] = a[st[id << 1]] <= a[st[id << 1 | 1]] ? st[id << 1] : st[id << 1 | 1];
    }
    void Build(int n)
    {
        this->n = n;
        Build(1, 1, n);
    }
    void Update(int id, int l, int r, const int &x, const int &v)
    {
        if (l > x || r < x)
            return;
        if (l == x && r == x)
        {
            a[l] = v;
            return;
        }
        Update(id << 1, l, (l + r) / 2, x, v);
        Update(id << 1 | 1, (l + r) / 2 + 1, r, x, v);
        st[id] = a[st[id << 1]] <= a[st[id << 1 | 1]] ? st[id << 1] : st[id << 1 | 1];
    }
    void Update(int x, int v)
    {
        Update(1, 1, n, x, v);
    }
    int Get(int id, int l, int r, const int &u, const int &v)
    {
        if (l > v || r < u)
            return 0;
        if (l >= u && r <= v)
            return st[id];
        int x = Get(id << 1, l, (l + r) / 2, u, v),
            y = Get(id << 1 | 1, (l + r) / 2 + 1, r, u, v);
        return a[x] <= a[y] ? x : y;
    }
    int Get(int l, int r)
    {
        return Get(1, 1, n, l, r);
    }
} f;

struct Request
{
    int v, d;
} a[N], b[N];

void Read()
{
    cin >> n >> m >> k;
    f.Build(n);
    for (int i = 1; i <= n; ++i)
        cin >> a[i].v >> a[i].d;
    for (int i = 1; i <= m; ++i)
        cin >> b[i].v >> b[i].d;
}

void Solve()
{
    sort(a + 1, a + n + 1, [&](const Request &x, const Request &y)
         { return x.d < y.d || (x.d == y.d && x.v < y.v); });
    sort(b + 1, b + m + 1, [&](const Request &x, const Request &y)
         { return x.v > y.v || (x.v == y.v && x.d < y.d); });

    for (int i = 1; i <= n; ++i)
        f.Update(i, a[i].v);

    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;

    ll ans(0);

    for (int i = 1; i <= m; ++i)
    {
        int l = 1, mid, h = n;
        while (l <= h)
        {
            mid = (l + h) / 2;
            if (a[mid].d < b[i].d)
                l = mid + 1;
            else
                h = mid - 1;
        }

        if (l > n)
            continue;
        int x = f.Get(l, n);

        if (b[i].v - f.a[x] > 0 && ((int)q.size() < k || b[i].v - f.a[x] > q.top().first))
        {
            if ((int)q.size() == k)
            {
                f.Update(q.top().second, a[q.top().second].v);
                ans -= q.top().first;
                q.pop();
            }

            ans += b[i].v - f.a[x];
            q.emplace(b[i].v - f.a[x], x);
            f.Update(x, Inf);
        }
    }

    cout << ans;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        //cout << "Case #" << _ << "\n";
        Read();
        Solve();
    }
    //cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}

Compilation message

hot.cpp: In function 'void read(T&)':
hot.cpp:12:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   12 |     register int c;
      |                  ^

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2252 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2252 KB	Output is correct
2	Correct	2 ms	2252 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2252 KB	Output is correct
2	Correct	2 ms	2252 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2252 KB	Output is correct
2	Correct	2 ms	2252 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	2508 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	51 ms	3804 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	107 ms	5624 KB	Output is correct
2	Correct	76 ms	4560 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	294 ms	11708 KB	Output is correct
2	Correct	169 ms	5956 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	559 ms	13796 KB	Output is correct
2	Correct	556 ms	12744 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	612 ms	14480 KB	Output is correct
2	Correct	778 ms	22492 KB	Output is correct
3	Correct	908 ms	22488 KB	Output is correct