Submission #957720

#	Time	Username	Problem	Language	Result	Execution time	Memory
957720		aykhn	Exhibition (JOI19_ho_t2)	C++17	0 / 100	1 ms	348 KiB

joi2019_ho_t2

#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 >= 0 ? b[i] : -inf);
        vector<int> v1;
        while (j >= 0 && a[j][0] > prev)
        {
            if (a[j][0] <= x)
            {
                v1.push_back(a[j][1]);
            }
            j--;
        }
        sort(v1.rbegin(), v1.rend());
        for (int x : v1)
        {
            make(0, sz, 0, x, min(mx, get(0, sz, 0, x, sz) + 1));
        }
    }
    cout << get(0, sz, 0, 0, sz) << '\n';
}

// 2 2 2 
// 1 1 1

// 1 1

Compilation message (stderr)

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
• Subtask 2: 0 / 40
• Subtask 3: 0 / 50