Subtask 2

• Bước đầu tìm vị trí ~L~ ~(1 \le L \le n)~ sao cho dãy số ~a_1, a_2, ..., a_L~ thoả mãn điều kiện ~a_1 \le a_2 \le ... \le a_L~ và ~L~ lớn nhất. Tương tự, tìm vị trí R ~(1 \le R \le m)~ sao cho dãy số ~b_R, b_{R + 1}, ..., b_m~ thoả mãn điều kiện ~b_R \le b_{R+1} \le ... \le b_m~ và ~R~ nhỏ nhất.
• Ta nhận thấy rằng: với mỗi phần tử ~a_i~ mà ~a_i \le b_j~ ~(1 \le i \le L, R \le j \le m)~ thì mọi ~a_k~ ~(1 \le k \le i)~ đều thoả mãn ~a_k \le b_j~. Dùng kĩ thuật hai con trỏ, ta duyệt ~i~ trên đoạn từ ~1~ đến ~L~, với mỗi phần tử ~a_i~, ta duy trì ~j~ sao cho ~a_i \le b_j~, kết quả là tổng khoảng cách từ ~1~ đến ~i~ và từ ~j~ đến ~m~ lớn nhất.

Code tham khảo

#include <bits/stdc++.h>
using namespace std;

int Find_Longest_Array(int n, int m, vector<int> a, vector<int> b) {
    int l = 0;
    int r = m - 1;
    while (l < n - 1 && a[l] <= a[l + 1]) l++;
    while (r > 0 && b[r] >= b[r - 1]) r--;

    int ans  = 0;
    for (int i = 0; i <= l; i++) {
        while (r < m && a[i] > b[r]) r++;
        if (r >= m) break;
        ans = max(ans, i + 1 + m - r);
    }

    return ans;
}

int main(void) {
    freopen("MARBLE.INP", "r", stdin);
    freopen("MARBLE.OUT", "w", stdout);
    int n,m;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    cin >> m;
    vector<int> b(m);
    for (int i = 0; i < m; i++) cin >> b[i];

    int res = Find_Longest_Array(n, m, a, b);
    cout << res;

    return 0;
}