Submission #948052

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
948052	2024-03-17T14:19:24 Z	GrindMachine	Hotel (CEOI11_hot)	C++17	100 / 100	529 ms	46432 KB

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

sort all rooms by cap
sort all orders by cost
process orders in dec ord of cost

let the curr order be of the form (cost,cap)
over all active rooms with capacity >= cap, find the room with min cost => let this room be i
if the curr order is picked, then it's optimal to match it with the ith room
conversely, if the ith room is chosen, then it needs to be matched with the curr order
this is true because if the ith room is matched with an order that has smaller cost, then it could be matched with the curr order for a higher profit

finding the min cost over all active rooms on a range can be done efficiently using a segtree
once a room is paired up with an order, it needs to be deactivated (set room cost to inf) 
at the end, sort the profits in non-inc order and pick values as long as possible and it's profitable (pick at most k values, dont pick values < 0) 

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

template<typename T>
struct segtree {
    // https://codeforces.com/blog/entry/18051

    /*=======================================================*/

    struct data {
        ll mn,ind;
    };

    data neutral = {inf2,-1};

    data merge(data &left, data &right) {
        data curr;

        if(left.mn <= right.mn) curr = left;
        else curr = right;
        
        return curr;
    }

    void create(int i, T v) {
        tr[i] = {v,i-n};
    }

    void modify(int i, T v) {
        tr[i] = {v,i-n};
    }

    /*=======================================================*/

    int n;
    vector<data> tr;

    segtree() {

    }

    segtree(int siz) {
        init(siz);
    }

    void init(int siz) {
        n = siz;
        tr.assign(2 * n, neutral);
    }

    void build(vector<T> &a, int siz) {
        rep(i, siz) create(i + n, a[i]);
        rev(i, n - 1, 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }

    void pupd(int i, T v) {
        modify(i + n, v);
        for (i = (i + n) >> 1; i; i >>= 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }

    data query(int l, int r) {
        data resl = neutral, resr = neutral;

        for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) resl = merge(resl, tr[l++]);
            if (!(r & 1)) resr = merge(tr[r--], resr);
        }

        return merge(resl, resr);
    }
};

void solve(int test_case)
{
    ll n,m,k; cin >> n >> m >> k;
    vector<pll> a(n+5), b(m+5);
    rep1(i,n){
        cin >> a[i].ss >> a[i].ff;
    }
    rep1(i,m){
        cin >> b[i].ff >> b[i].ss;
    }

    sort(a.begin()+1,a.begin()+n+1);
    sort(b.begin()+1,b.begin()+m+1);
    segtree<ll> st(n+5);
    rep1(i,n) st.pupd(i,a[i].ss);

    vector<ll> profits;

    rev(i,m,1){
        auto [cost,cap] = b[i];
        ll pos = lower_bound(a.begin()+1,a.begin()+n+1,make_pair(cap,-1ll))-a.begin();
        auto [mn,ind] = st.query(pos,n);
        if(ind != -1){
            profits.pb(cost-mn);
            st.pupd(ind,inf2);
        }
    }

    sort(rall(profits));
    ll ans = 0;

    rep(i,sz(profits)){
        if(i >= k) break;
        if(profits[i] < 0) break;
        ans += profits[i];
    }

    cout << ans << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	63 ms	7460 KB	Output is correct
2	Correct	42 ms	5936 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	182 ms	19088 KB	Output is correct
2	Correct	104 ms	11216 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	366 ms	38744 KB	Output is correct
2	Correct	401 ms	39060 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	394 ms	45400 KB	Output is correct
2	Correct	482 ms	46432 KB	Output is correct
3	Correct	529 ms	44640 KB	Output is correct

Submission #948052

Compilation message