Submission #383010

#	Time	Username	Problem	Language	Result	Execution time	Memory
383010		valerikk	Exam (eJOI20_exam)	C++17	100 / 100	238 ms	122988 KiB

exam

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

const int N = 5005;
const int M = 1e5 + 7;

int n;
int a[M], b[M];
bool ok[N][N];
int dp[N][N];
int t[2 * M];

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 solve_b_equal() {
    int B = b[0];
    vector<int> inds;
    inds.push_back(-1);
    for (int i = 0; i < n; ++i) {
        if (a[i] > B) inds.push_back(i); 
    }
    inds.push_back(n);
    int ans = 0;
    for (int i = 0; i + 1 < inds.size(); ++i) {
        bool ok = false;
        for (int j = inds[i] + 1; j < inds[i + 1]; ++j) {
            ok |= a[j] == B;
        }
        if (ok) ans += inds[i + 1] - inds[i] - 1;
    }
    cout << ans << endl;
}

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 (int)last.size() - 1;
}

void solve_a_distinct() {
    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() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    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 b_equal = true;
    for (int i = 1; i < n; ++i) b_equal &= b[i] == b[i - 1];
    if (b_equal) {
        solve_b_equal();
        return 0;
    }
    
    vector<int> A;
    for (int i = 0; i < n; ++i) A.push_back(a[i]);
    sort(A.begin(), A.end());
    bool a_distinct = true;
    for (int i = 1; i < n; ++i) a_distinct &= A[i] != A[i - 1];
    if (a_distinct) {
        solve_a_distinct();
        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;
}

Compilation message (stderr)

exam.cpp: In function 'void solve_b_equal()':
exam.cpp:38:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (int i = 0; i + 1 < inds.size(); ++i) {
      |                     ~~~~~~^~~~~~~~~~~~~

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