# MorsLin 的博客

### 题解 P1704 【寻找最优美做题曲线】

posted on 2019-05-18 17:23:20 | under 题解 |

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define LL long long
using namespace std;
LL k = 0, f = 1; char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9')
k = k * 10 + c - 48, c = getchar();
return k * f;
}
int p[500010], a[500010], ans[500010], b[500010], tot;
int main() {
for(int i = 1; i <= k; ++i) p[i] = read();
for(int i = 1; i <= n; ++i) a[i] = read();
sort(p+1, p+k+1);
for(int i = 1; i <= p[1]; ++i)
if(a[i] < a[p[1]]) ans[++tot] = a[i];
ans[++tot] = a[p[1]];
for(int i = 2; i <= k; ++i) {
if(a[p[i-1]] >= a[p[i]]) {
printf("impossible\n"); return 0;
}
for(int j = p[i-1]+1; j <= p[i]; ++j) {
if(a[j] < a[p[i]] && a[j] > a[p[i-1]]) ans[++tot] = a[j];
}
ans[++tot] = a[p[i]];
}
for(int i = p[k]; i <= n; ++i)
if(a[i] > a[p[k]]) ans[++tot] = a[i];
int cnt = 0;
for(int i = 1; i <= tot; ++i) {
if(ans[i] > b[cnt]) b[++cnt] = ans[i];
else {
int pos = lower_bound(b+1, b+cnt+1, ans[i]) - b;
b[pos] = ans[i];
}
}
cout << cnt << endl;
return 0;
}