Submission #1356424

#TimeUsernameProblemLanguageResultExecution timeMemory
1356424gayExhibition (JOI19_ho_t2)C++20
0 / 100
0 ms344 KiB
#include <bits/stdc++.h>
#include <experimental/random>
#include <random>

//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;

using namespace std;

using ld = long double;
using ll = long long;

const ll INF = 3e18, MOD = 1e9 + 7;

void solve();

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int q = 1;
    //cin >> q;
    while (q--) {
        solve();
    }
}

struct seg_tree {
    vector<ll> tree;
    void change(ll v, ll vl, ll vr, ll pos, ll x) {
        if (vr - vl == 1) {
            tree[v] = max(tree[v], x);
            return;
        }
        ll m = (vl + vr) / 2;
        if (pos < m) {
            change(2 * v, vl, m, pos, x);
        } else {
            change(2 * v + 1, m, vr, pos, x);
        }
        tree[v] = max(tree[2 * v], tree[2 * v + 1]);
    }
    ll get(ll v, ll vl, ll vr, ll l, ll r) {
        if (vl >= r || vr <= l) {
            return 0;
        }
        if (vl >= l && vr <= r) {
            return tree[v];
        }
        ll m = (vl + vr) / 2;
        return max(get(2 * v, vl, m, l, r), get(2 * v + 1, m, vr, l, r));
    }
};

void solve() {
    ll n, m; cin >> n >> m;
    vector<pair<ll, ll>> a(n);
    vector<ll> cord;
    for (int i = 0; i < n; i++) {
        cin >> a[i].first >> a[i].second;
        cord.push_back(a[i].second);
    }
    sort(a.rbegin(), a.rend());
    vector<ll> c(m);
    for (int i = 0; i < m; i++) {
        cin >> c[i];
    }
    sort(c.rbegin(), c.rend());
    vector<ll> cnt(n);
    ll id = 0;
    for (int i = 0; i < n; i++) {
        while (id < m && c[id] >= a[i].first) {
            id++;
        }
        cnt[i] = id;
    }
    sort(cord.begin(), cord.end());
    cord.resize(unique(cord.begin(), cord.end()) - cord.begin());
    ll len = (int)cord.size();
    seg_tree t;
    t.tree.resize(4 * len);
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        if (cnt[i] == 0) continue;
        ll idx = lower_bound(cord.begin(), cord.end(), a[i].second) - cord.begin();
        ll cur = min(cnt[i], t.get(1, 0, len, idx, len) + 1);
        ans = max(ans, cur);
        t.change(1, 0, len, idx, cur);
    }
    cout << ans;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...