제출 #365156

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
365156		Lam_lai_cuoc_doi	Exhibition (JOI19_ho_t2)	C++17	0 / 100	1 ms	364 KiB

joi2019_ho_t2

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

const bool typetest = 0;
const int N = 1e5 + 5;
const ll Inf = 1e17;
int n, m, ans(0);
int c[N], dp[N], last[N];
struct picture
{
    int s, v;
    bool operator<(const picture &a) const
    {
        return s < a.s || (s == a.s && v < a.v);
    }
} a[N];
struct com
{
    bool operator()(const int &x, const int &y) const
    {
        return a[x].v < a[y].v || (a[x].v == a[y].v && last[x] < last[y]);
    }
};
set<int, com> s;

void Read()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> a[i].s >> a[i].v;
    for (int i = 1; i <= m; ++i)
        cin >> c[i];
    sort(a + 1, a + n + 1);
    sort(c + 1, c + m + 1);
}

void Solve()
{
    for (int i = 1; i <= n; ++i)
    {
        last[i] = m;
        auto t = s.lower_bound(i);
        if (t == s.begin())
        {
            dp[i] = 1;
            last[i] = lower_bound(c + 1, c + m + 1, a[i].s) - c;
        }
        else
        {
            t = prev(t);
            dp[i] = dp[*t] + 1;
            last[i] = max(last[*t] + 1, (int)(lower_bound(c + 1, c + m + 1, a[i].s) - c));
        }
        if (last[i] <= m)
        {
            s.insert(i);
            ans = max(ans, dp[i]);
        }
    }
    cout << ans;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        Read();
        Solve();
    }
}

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