Submission #1295711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295711		fairkrash	Exhibition (JOI19_ho_t2)	C++20	0 / 100	1 ms	572 KiB

joi2019_ho_t2

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
ll INF = 1e18;
ll MOD = 1e9 + 7;

vector<ll> z;
vector<ll> tree;

ll sum(ll v, ll vl, ll vr, ll l, ll r) {
    if (l >= vr || vl >= r) {
        return 0;
    }
    if (l <= vl && r >= vr) {
        return tree[v];
    }
    ll mid = (vr + vl) / 2;
    return max(sum(v * 2, vl, mid, l, r), sum(v * 2 + 1, mid, vr, l, r));
}

void change(ll v, ll vl, ll vr, ll ind, ll x) {
    if (vr - vl == 1) {
        tree[v] = x;
        return;
    }
    ll mid = (vr + vl) / 2;
    if (ind < mid) {
        change(v * 2, vl, mid, ind, x);
    } else {
        change(v * 2 + 1, mid, vr, ind, x);
    }
    tree[v] = max(tree[v * 2], tree[v * 2 + 1]);
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll n, m;
    cin >> n >> m;
    vector<pair<ll, ll>> s(n);
    z.assign(n, 0);
    vector<ll> c(m);
    map<ll, ll> mp;
    for (ll i = 0; i < n; i++) {
        cin >> s[i].first >> s[i].second;
        mp[s[i].second] = 0;
    }
    ll d = 0;
    for (auto to: mp) {
        mp[to.first] = d;
        d++;
    }
    for (ll i = 0; i < s.size(); i++) {
        s[i].second = -mp[s[i].second];
    }
    std::sort(s.begin(), s.end());
    for (ll i = 0; i < s.size(); i++) {
        z[i] = -s[i].second;
    }
    for (ll i = 0; i < m; i++) {
        cin >> c[i];
    }
    sort(c.rbegin(), c.rend());
    tree.assign((d + 2) * 4, 0);
    for (ll i = n - 1; i >= 0; i--) {
        ll k = sum(1, 0, d + 1, z[i], d + 1);
        if (k == m) {
            break;
        }
        if (c[k] >= s[i].first) {
            change(1, 0, d + 1, z[i], k + 1);
        }
    }
    cout << tree[1] << endl;
}
// 4 2
// 28 1
// 8 8
// 6 10
// 16 9
// 4
// 3

• Subtask 1: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 50