oj.uz

Submission #957538

# Submission time Handle Problem Language Result Execution time Memory
957538 2024-04-04T01:43:19 Z aykhn Exhibition (JOI19_ho_t2) C++17
0 / 100
 1 ms 348 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define inf 0x3F3F3F3F

vector<int> st;

void make(int l, int r, int x, int ind, int val)
{
    if (l + 1 == r)
    {
        st[x] = max(st[x], val);
        return;
    }
    int mid = (l + r) >> 1;
    if (ind < mid) make(l, mid, 2*x + 1, ind, val);
    else make(mid, r, 2*x + 2, ind, val);
    st[x] = max(st[2*x + 1], st[2*x + 2]);
}
int get(int l, int r, int x, int lx, int rx)
{
    if (l >= rx || r <= lx) return 0;
    if (l >= lx && r <= rx) return st[x];
    int mid = (l + r) >> 1;
    return max(get(l, mid, 2*x + 1, lx, rx), get(mid, r, 2*x + 2, lx, rx));
}
 
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    int n, m, sz = 1;
    cin >> n >> m;
    int b[m];
    array<int, 2> a[n];
    vector<int> mp;
    for (array<int, 2> &x : a) 
    {
        cin >> x[0] >> x[1];
        mp.push_back(x[0]);
        mp.push_back(x[1]);
    }
    for (int &i : b) 
    {
        cin >> i;
        mp.push_back(i);
    }
    sort(mp.begin(), mp.end());
    mp.resize(unique(mp.begin(), mp.end()) - mp.begin());
    while (sz < mp.size()) sz <<= 1;
    st.assign(sz << 1, 0);
    for (array<int, 2> &x : a) x[0] = lower_bound(mp.begin(), mp.end(), x[0]) - mp.begin(), x[1] = lower_bound(mp.begin(), mp.end(), x[1]) - mp.begin();
    for (int &i : b) i = lower_bound(mp.begin(), mp.end(), i) - mp.begin();
    sort(b, b + m);
    sort(a, a + n);
    int j = n - 1;
    for (int i = m - 1; i >= 0;)
    {
        int x = b[i];
        while (i >= 0 && b[i] == x) i--;
        int mx = m - i - 1;
        int prev = (i ? b[i] : -inf);
        while (j >= 0 && a[j][0] > prev)
        {
            if (a[j][0] <= b[m - 1])
            {
                // cout << mx << ' ' << j << ": " << min(mx, get(0, sz, 0, a[j][1], sz) + 1) << '\n';
                make(0, sz, 0, a[j][1], min(mx, get(0, sz, 0, a[j][1], sz) + 1));
            }
            j--;
        }
    }
    cout << get(0, sz, 0, 0, sz) << '\n';
}
// 15 2 19 3 0 18 5 9
// 4 11 12 13 14 17 21 22
// 1 6 7 8 10 16 20 23

// 0 1 2 3 4 5 6 7

Compilation message

joi2019_ho_t2.cpp: In function 'int main()':
joi2019_ho_t2.cpp:52:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     while (sz < mp.size()) sz <<= 1;
      |            ~~~^~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -