| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1104238 | manhlinh1501 | Exam (eJOI20_exam) | C++17 | 0 ms | 0 KiB |
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>
using namespace std;
using i64 = long long;
const int MAXN = 2e5 + 5;
#define left ___left
#define right ___right
#define ALL(a) (a).begin(), (a).end()
using pii = pair<int, int>;
int N;
int a[MAXN];
int b[MAXN];
int left[MAXN];
int right[MAXN];
void compress() {
map<int, int> comp;
for(int i = 1; i <= N; i++) comp[a[i]] = 1;
for(int i = 1; i <= N; i++) comp[b[i]] = 1;
int c = 0;
for(auto &[x, y] : comp) y = ++c;
for(int i = 1; i <= N; i++) a[i] = comp[a[i]];
for(int i = 1; i <= N; i++) b[i] = comp[b[i]];
}
namespace subtask2 {
bool is_subtask() {
for(int i = 1; i < N; i++) {
if(b[i] != b[i + 1]) return false;
}
return true;
}
int cnt[MAXN];
void solution() {
if(is_subtask() == false) return;
for(int i = 1; i <= N; i++) {
if(a[i] == b[i]) {
cnt[left[i]]++;
cnt[right[i] + 1]--;
}
}
for(int i = 1; i <= N; i++) cnt[i] += cnt[i - 1];
int ans = 0;
for(int i = 1; i <= N; i++) ans += (cnt[i] > 0);
cout << ans;
exit(0);
}
}
namespace subtask3 {
const int MAXN = 5e3 + 5;
bool is_subtask() {
return is_sorted(a + 1, a + N + 1);
}
int dp[MAXN][MAXN];
void solution() {
if(is_subtask() == false) return;
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= i; j++) {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
if(a[i] == b[j])
dp[i][j] = max(dp[i][j], max(dp[i - 1][j - 1], dp[i][j - 1]) + 1);
}
}
int ans = 0;
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= i; j++)
ans = max(ans, dp[i][j]);
}
cout << ans;
exit(0);
}
}
namespace subtask4 {
bool is_subtask() {
vector<int> b;
for(int i = 1; i <= N; i++) b.emplace_back(a[i]);
sort(ALL(b));
for(int i = 1; i < N; i++) {
if(b[i] == b[i - 1]) return false;
}
return true;
}
namespace ST {
int N;
int tree[MAXN * 4];
void init(int _N) {
N = _N;
}
void update(int p, int x) {
int id = 1, l = 1, r = N;
while(l <= r) {
int m = (l + r) / 2;
if(p <= m) {
id = id * 2;
r = m;
} else {
id = id * 2 + 1;
l = m + 1;
}
}
tree[id] = x;
while(id = 1) {
id >>= 1;
tree[id] = max(tree[id * 2], tree[id * 2 + 1]);
}
}
int get(int id, int l, int r, int u, int v) {
if(r < u or l > v) return 0;
if(u <= l and r <= v) return tree[id];
int m = (l + r) / 2;
return max(get(id * 2, l, m, u, v), get(id * 2 + 1, m + 1, r, u, v));
}
int get(int l, int r) {
return get(1, 1, N, l, r);
}
}
int pos[MAXN];
void solution() {
if(is_subtask() == false) return;
ST::init(N);
for(int i = 1; i <= N; i++) pos[a[i]] = i;
for(int i = 1; i <= N; i++) {
int p = pos[b[i]];
if(p == 0) continue;
if(left[p] <= i and i <= right[p])
ST::update(p, ST::get(p) + 1);
}
cout << ST::tree[1];
exit(0);
}
}
namespace subtask6 {
const int MAXN = 5e3 + 5;
int dp[MAXN][MAXN];
bool is_subtask() {
return N < MAXN;
}
void solution() {
if(is_subtask() == false) return;
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= N; j++) {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
if(a[i] == b[j] and left[i] <= j and j <= right[i])
dp[i][j] = max(dp[i][j], max(dp[i - 1][j - 1], dp[i][j - 1]) + 1);
}
}
int ans = 0;
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= N; j++)
ans = max(ans, dp[i][j]);
}
cout << ans;
exit(0);
}
}
signed main() {
#define task "code"
if(fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N;
for(int i = 1; i <= N; i++) cin >> a[i];
for(int i = 1; i <= N; i++) cin >> b[i];
compress();
for(int i = 1; i <= N; i++) {
left[i] = i - 1;
while(left[i] > 0 and a[left[i]] <= a[i])
left[i] = left[left[i]];
}
for(int i = N; i >= 1; i--) {
right[i] = i + 1;
while(right[i] <= N and a[right[i]] <= a[i])
right[i] = right[right[i]];
}
for(int i = 1; i <= N; i++) {
left[i]++;
right[i]--;
}
// subtask2::solution();
// subtask3::solution();
// subtask6::solution();
subtask4::solution();
return (0 ^ 0);
}