#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
#define ll long long
#define ar array
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
// --------------- SOLUTION --------------- //
const int N = 1e5+5;
int n;
int a[N], b[N];
int t[4 * N];
int nm[N], pm[N];
int dp[5001][5001];
void pre() {
stack<int> s;
for (int i = 1; i <= n; ++i) {
while (!s.empty() && a[s.top()] <= a[i])
s.pop();
if (s.empty())
pm[i] = 0;
else
pm[i] = s.top();
s.push(i);
}
while (!s.empty())
s.pop();
for (int i = n; i >= 1; --i) {
while (!s.empty() && a[s.top()] <= a[i])
s.pop();
if (s.empty())
nm[i] = n + 1;
else
nm[i] = s.top();
s.push(i);
}
}
int t[N * 4];
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));
}
map <int, int> mp;
int segTreeSolve() {
for (int i = 1; i <= n; ++i)
mp[a[i]] = i;
for (int i = 1; i <= n; ++i) {
if (mp.find(b[i]) == mp.end())
continue;
int x = mp[b[i]];
if (pm[x] < i && i < nm[x]) {
ubd(1, n, x, qry(1, n, 1, x, 1) + 1, 1);
}
}
return t[1];
}
int less5000() {
int ans = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (a[i] == b[j] && pm[i] < j && j < nm[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 (int i = 1; i <= n + 1; ++i)
for (int j = 1; j <= n + 1; ++j)
ans = max(ans, dp[i][j]);
return ans;
}
// int p[N];
// int sameBs() {
// for (int i = 1; i <= n; ++i) {
// p[i] = p[i - 1];
// if (a[i] == b[i])
// ++p[i];
// }
// next_max[0] = 0;
// for (int i = 1; i <= n; ++i) {
// if (a[i] > b[i]) {
// next_max[i] = i;
// }
// else {
// next_max[i] = next_max[i - 1];
// }
// }
// prev_max[n + 1] = n + 1;
// for (int i = n; i >= 1; --i) {
// if (a[i] > b[i]) {
// prev_max[i] = i;
// }
// else {
// prev_max[i] = prev_max[i + 1];
// }
// }
// int ans = 0;
// for (int i = 1; i <= n; ++i) {
// if (a[i] <= b[i] && p[prev_max[i] - 1] - p[next_max[i]] > 0) {
// ++ans;
// }
// }
// return ans;
// }
void solve() {
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i];
for (int i = 1; i <= n; ++i)
cin >> b[i];
// bool ok = true;
// for (int i = 1; i <= n; ++i)
// if (b[i] != b[1]) {
// ok = false;
// break;
// }
// if (ok) {
// cout << sameBs() << "\n";
// return;
// }
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;
}
Compilation message
exam.cpp:43:5: error: redefinition of 'int t [400020]'
43 | int t[N * 4];
| ^
exam.cpp:15:5: note: 'int t [400020]' previously declared here
15 | int t[4 * N];
| ^
