This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
#define ll long long
#define ar array
#define f first
#define s second
#define mpr make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define FOR(i, a, b) for(auto i = a; i < b; i++)
#define FORD(i, a, b) for(auto i = a - 1; i >= b; i--)
#define trav(x, v) for(auto x : v)
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fileio freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
// --------------- SOLUTION --------------- //
const int N = 1e5+5;
int n;
int a[N], b[N];
int t[4 * N];
int next_max[N], prev_max[N];
int dp[5001][5001];
map <int, int> mp;
void pre() {
stack<int> s;
FOR(i, 1, n + 1) {
while (!s.empty() && a[s.top()] <= a[i])
s.pop();
if (s.empty())
next_max[i] = -1;
else
next_max[i] = s.top();
s.push(i);
}
while (!s.empty())
s.pop();
FORD(i, n + 1, 1) {
while (!s.empty() && a[s.top()] <= a[i])
s.pop();
if (s.empty())
prev_max[i] = n + 1;
else
prev_max[i] = s.top();
s.push(i);
}
}
void ubd(int tl, int tr, int x, int y, int pos) {
if (tl == tr) {
t[pos] = y;
return;
}
int m = (tl + tr) / 2;
if (x <= m)
ubd(tl, m, x, y, pos * 2);
else
ubd(m + 1, tr, x, y, pos * 2 + 1);
t[pos] = max(t[pos * 2], t[pos * 2 + 1]);
}
int qry(int tl, int tr, int l, int r, int pos) {
if (l > r)
return 0;
if (tl == l && tr == r)
return t[pos];
int m = (tl + tr) / 2;
return max(qry(tl, m, l, min(m, r), pos * 2),
qry(m + 1, tr, max(m + 1, l), r, pos * 2 + 1));
}
int segTreeSolve() {
FOR(i, 1, n + 1) {
mp[a[i]] = i;
}
FOR(i, 1, n + 1) {
if (mp.find(b[i]) == mp.end()) continue;
if (next_max[mp[b[i]]] < i && prev_max[mp[b[i]]] > i) ubd(1, n, mp[b[i]], qry(1, n, 1, mp[b[i]], 1) + 1, 1);
}
return t[1];
}
int less5000() {
int ans = 0;
FOR(i, 1, n + 1) {
FOR(j, 1, n + 1) {
if (a[i] == b[j] && next_max[i] < j && j < prev_max[i]) {
dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + 1);
}
dp[i][j + 1] = max(dp[i][j + 1], dp[i][j]);
dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
}
}
FOR(i, 1, n + 2)
FOR(j, 1, n + 2)
ans = max(ans, dp[i][j]);
return ans;
}
void solve() {
cin >> n;
FOR(i, 1, n + 1) {
cin >> a[i];
}
FOR(i, 1, n + 1) {
cin >> b[i];
}
pre();
if (n <= 5000) {
cout << less5000() << "\n";
return;
}
cout << segTreeSolve() << "\n";
}
int main() {
fastio;
// fileio;
int tests = 1;
// cin >> tests;
while (tests--) {
solve();
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |