Submission #916556

#TimeUsernameProblemLanguageResultExecution timeMemory
916556viwlesxqExhibition (JOI19_ho_t2)C++17
100 / 100
62 ms8024 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define size(x) (int)x.size()

template<class S, class T>
bool chmin(S &a, const T &b) {
    return a > b && (a = b) == b;
}
template<class S, class T>
bool chmax(S &a, const T &b) {
    return a < b && (a = b) == b;
}
const int inf = 1e9 + 7;
const int INF = 1e18 + 7;
const int mod = 1e9 + 7;

void pair_sort(vector<int> &a, vector<int> &b, int n) {
    vector<pair<int, int>> v;
    for (int i = 0; i < n; ++i) v.push_back({a[i], b[i]});
    sort(all(v));
    for (int i = 0; i < n; ++i) a[i] = v[i].first, b[i] = v[i].second;
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m; cin >> n >> m;
    vector<int> s(n), v(n), c(m);
    for (int i = 0; i < n; ++i) cin >> s[i] >> v[i];
    for (int i = 0; i < m; ++i) cin >> c[i];
    sort(all(c));
    pair_sort(v, s, n);
    int lo = 0, hi = min(n, m) + 1;
    while (lo + 1 < hi) {
        int mid = (lo + hi) / 2;
        deque<int> arr;
        for (int i = m - mid; i < m; ++i) arr.push_back(c[i]);
        for (int i = 0; i < n; ++i) {
            if (!arr.empty() && s[i] <= arr.front()) {
                arr.pop_front();
            }
        }
        if (arr.empty()) lo = mid;
        else hi = mid;
    }
    cout << lo;
} 
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...