Submission #1400916

#TimeUsernameProblemLanguageResultExecution timeMemory
1400916d4n13lProblem Setter (NOI24_problemsetter)C++20
100 / 100
69 ms8240 KiB
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int mod = 998244353;
const int INF = 1e15;
const int mag = 1000000000;

void solve() {
    int c, p;
    cin >> c >> p;
    vector <pair <int, int> > contest(c), problem(p);
    for (int i = 0; i< c; i++) {
        cin >> contest[i].first >> contest[i].second;
    }
    sort (contest.begin(), contest.end());
    for (int i = 0; i< p; i++) {
        cin >> problem[i].first >> problem[i].second;
    }
    vector <int> pref(c);
    for (int i = 0; i< c; i++) {
        if (i==0) {
            pref[i]=contest[i].second;
        } else {
            pref[i]=max(pref[i-1], contest[i].second);
        }
    }
    int ans = 0;
    for (int i = 0; i< p; i++) {
        int q = problem[i].first, d = problem[i].second;
        auto it = upper_bound(contest.begin(), contest.end(), make_pair(q,INF));
        if (it!=contest.begin()) {
            it--;
            int idx = it-contest.begin();
            if (pref[idx]>d) {
                ans+=pref[idx]-d;
            }
        }
    }
    cout << ans << endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1;
    //cin >> t;
    while (t--) {
        solve();
    }
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...