oj.uz

Submission #365159

# Submission time Handle Problem Language Result Execution time Memory
365159 2021-02-11T03:53:32 Z Lam_lai_cuoc_doi Exhibition (JOI19_ho_t2) C++17
0 / 100
 1 ms 364 KB 
#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);
            while(t != s.begin() && last[*t] == m)
                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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Incorrect 1 ms 364 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Incorrect 1 ms 364 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Incorrect 1 ms 364 KB Output isn't correct
6 Halted 0 ms 0 KB -