Submission #895845

#TimeUsernameProblemLanguageResultExecution timeMemory
895845tvladm2009Exam (eJOI20_exam)C++17
88 / 100
91 ms124264 KiB
#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; } 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]; 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...