#include <bits/stdc++.h>
using namespace std;
#define BIT(x, i) (((x) >> (i)) & 1)
template <class X, class Y>
bool maximize(X &x, Y y) {
if (x < y) return x = y, true;
else return false;
}
template <class T>
void remove_dup(vector <T> &v) {
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end()) - v.begin());
}
int POS(int x, vector <int> &v) {
return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}
const int inf = (int) 1e9 + 7;
int n;
#define MAX_N 100'100
int a[MAX_N + 2], b[MAX_N + 2];
#undef MAX_N
namespace subtask2 {
bool check() {
return (*max_element(b + 1, b + 1 + n) == *min_element(b + 1, b + 1 + n));
}
void solve() {
int ans = 0, cnt = 0;
bool ok = false;
a[n + 1] = inf;
for (int i = 1; i <= n + 1; ++i) {
if (a[i] > b[1]) {
if (ok) ans += cnt;
cnt = 0;
ok = false;
} else {
++cnt;
if (a[i] == b[1]) ok = true;
}
}
cout << ans;
}
};
namespace subtask3 {
bool check() {
for (int i = 1; i < n; ++i) {
if (a[i] >= a[i + 1]) return false;
}
return (n <= 5000);
}
int f[5050][5050];
//f[i][j]: ap dung nhung thay doi tu A[1] -> A[i] cho nhung thang tu 1 -> j
void solve(){
int N = n;
vector <int> lef(n + 2), rig(n + 2);
for(int i = 1; i <= N; i++){
lef[i] = i - 1;
while(lef[i] > 0 && a[i] >= a[lef[i]]) lef[i] = lef[lef[i]];
}
for(int i = N; i >= 1; i--){
rig[i] = i + 1;
while(rig[i] <= N && a[i] >= a[rig[i]]) rig[i] = rig[rig[i]];
}
int ans = 0;
for(int j = 1; j <= n; j++){
for(int i = 1; i <= n; i++){
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
if(a[i] == b[j] && lef[i] < j && j < rig[i]){
maximize(f[i][j], f[i][j - 1] + 1);
}
maximize(ans, f[i][j]);
}
}
cout << ans << '\n';
}
};
int main() {
ios_base::sync_with_stdio(false);cin.tie(nullptr);
if (fopen("test.inp","r")) {
freopen("test.inp","r",stdin);
freopen("test.out","w",stdout);
}
cin >> n;
vector <int> v;
for (int i = 1; i <= n; ++i) cin >> a[i], v.push_back(a[i]);
for (int i = 1; i <= n; ++i) cin >> b[i], v.push_back(b[i]);
remove_dup(v);
for (int i = 1; i <= n; ++i) {
a[i] = POS(a[i], v);
b[i] = POS(b[i], v);
}
// if (subtask2 :: check()) return subtask2 :: solve(), 0;
// if (subtask3 :: check())
return subtask3 :: solve(), 0;
return 0;
}
Compilation message (stderr)
exam.cpp: In function 'int main()':
exam.cpp:96:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
96 | freopen("test.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
exam.cpp:97:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
97 | freopen("test.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# | 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... |