Submission #895846

#	Time	Username	Problem	Language	Result	Execution time	Memory
895846		tvladm2009	Exam (eJOI20_exam)	C++17	100 / 100	78 ms	123992 KiB

exam

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 5e3 + 7;
const int M = 1e5 + 7;
int a[M], b[M];
bool ok[N][N];
int dp[N][N];
int t[2 * M];
int n;

void build_tree() {
    for (int i = 0; i < n; ++i) t[i + n] = a[i];
    for (int i = n - 1; i > 0; --i) t[i] = max(t[2 * i], t[2 * i + 1]);
}

int get_max(int l, int r) {
    l += n, r += n;
    int res = 0;
    while (l < r) {
        if (l & 1) res = max(res, t[l++]);
        if (r & 1) res = max(res, t[--r]);
        l >>= 1, r >>= 1;
    }
    return res;
}

void subtask2() {
    vector<int> A(n + 1), B(n + 1);
    for (int i = 1; i <= n; ++i) {
        A[i] = a[i - 1];
        B[i] = b[i - 1];
    }
    vector<int> l(n + 1), r(n + 1);
    vector<int> stk;
    for (int i = 1; i <= n; ++i) {
        while (!stk.empty() && A[i] >= A[stk.back()]) {
            stk.pop_back();
        }
        if (stk.empty()) l[i] = 1;
        else l[i] = stk.back() + 1;
        stk.push_back(i);
    }
    stk.clear();
    for (int i = n; i >= 1; --i) {
        while (!stk.empty() && A[i] >= A[stk.back()]) {
            stk.pop_back();
        }
        if (stk.empty()) r[i] = n;
        else r[i] = stk.back() - 1;
        stk.push_back(i);
    }
    vector<int> mars(n + 10, 0);
    int want = B[1];
    for (int i = 1; i <= n; ++i) {
        if (A[i] == want) {
            ++mars[l[i]];
            --mars[r[i] + 1];
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        mars[i] += mars[i - 1];
        if (mars[i] > 0) {
            ++ans;
        }
    }
    cout << ans << "\n";
}

int find_lis(vector<int> arr) {
    vector<int> last;
    last.push_back(0);
    for (int x : arr) {
        if (last.back() <= x) {
            last.push_back(x);
        } else {
            int pos = upper_bound(last.begin(), last.end(), x) - last.begin() - 1;
            last[pos + 1] = x;
        }
    }
    return last.size() - 1;
}
 
void subtask3() {
    build_tree();
    map<int, int> where;
    for (int i = 0; i < n; ++i) where[a[i]] = i;
    vector<int> arr;
    for (int i = 0; i < n; ++i) {
        if (where.count(b[i])) {
            int pos = where[b[i]];
            int l = i, r = pos;
            if (l > r) swap(l, r);
            if (get_max(l, r + 1) <= b[i]) arr.push_back(pos);
        }
    }
    cout << find_lis(arr) << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    bool same = 1;
    for (int i = 1; i < n; i++) same &= b[i] == b[0];
    if (same) {
        subtask2();
        return 0;
    }
    if (n > 5e3) {
        subtask3();
        return 0;
    }
    for (int i = 0; i < n; i++) {
        ok[i][i] = true;
        for (int j = i - 1; j >= 0; j--) {
            if (a[j] > a[i]) break;
            ok[j][i] = true;
        }
        for (int j = i + 1; j < n; j++) {
            if (a[j] > a[i]) break;
            ok[j][i] = true;
        }
    }
    for (int i = 0; i < n; i++) {
        if (ok[0][i] && b[0] == a[i]) {
            dp[0][i] = 1;
        }
    }
    for (int i = 1; i < n; i++) {
        int mx = 0;
        for (int j = 0; j < n; j++) {
            mx = max(mx, dp[i - 1][j]);
            if (ok[i][j]) {
                dp[i][j] = mx;
                if (b[i] == a[j]) ++dp[i][j];
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) ans = max(ans, dp[n - 1][i]);
    cout << ans << endl;
    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 23 / 23
• Subtask 5: 16 / 16
• Subtask 6: 22 / 22