```
// luogu-judger-enable-o2
//每一个不曾AC的日子都是一种遗憾
#include<stdio.h>
#include<vector>
#include<algorithm>
#define MAXN 100005
using namespace std;
int dis=1;
int a[MAXN],d[MAXN];
vector<int> hei;
inline int LIS()
{
d[1]=a[1];
int len=1;
for(int i=2;i<dis;i++)
{
if (a[i]>=d[len])d[++len]=a[i];
else
{
int j=upper_bound(d+1,d+len+1,a[i])-d;
d[j]=a[i];
}
}
return len;
}
int main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
int sum=0;
while(scanf("%d",&a[dis])==1)
{
vector<int>::iterator result;
sort(hei.begin(),hei.end());
result=lower_bound(hei.begin(),hei.end(),a[dis]);
if(result-hei.end()>=0)
{
sum++;
hei.push_back(a[dis]);
}
else *result=a[dis];
dis++;
}
for(int k=1;k<dis;k++)
a[k]=-a[k];
printf("%d\n",LIS());
printf("%d",sum);
return 0;
}
```
吸了氧气才过，比不吸氧气快了N倍，这份代码的STL依赖症已经到了这种地步吗？
by xiangling @ 2018-06-24 18:59:38
@[rainman](/space/show?uid=55804) 66666
by happyZYM @ 2018-06-24 19:29:54
@[rainman](/space/show?uid=55804) 您需要臭氧……
by 引领天下 @ 2018-06-24 20:02:12
@[rainman](/space/show?uid=55804) 盗一发图
by 引领天下 @ 2018-06-24 20:03:14
我一年前那份代码重新测没开O2最慢的点也就不到50ms，同样是std::lower_bound，没看懂写std::sort和std::vector有什么意义。
by SeKong @ 2018-06-24 20:04:05
一群红名大佬（除了我）在欺负小绿人.....
by happyZYM @ 2018-06-24 20:16:19
@[happyZYM](/space/show?uid=87248) 一群红名大佬（除了我这个红名蒟蒻）在欺负小绿人
by 引领天下 @ 2018-06-24 20:50:16
一群红名大佬（除了我这个红名蒟蒻）在欺负小绿人.....
by 诸葛村夫 @ 2018-07-03 16:06:12
@[引领天下](/space/show?uid=39863)
~~小绿人变成小橙人啦~~
by xiangling @ 2018-07-15 18:46:17
@[rainman](/space/show?uid=55804) ~~不久就是小红人啦~~
by 引领天下 @ 2018-07-15 20:02:14