题目要求时间复杂度达到O(nlogn)才能过关，把100pts的代码优化了一下，但是优化后变成70pts了，其余的点都是TLE。

优化后的整体思路是： 先求第一问，将导弹高度和dp值存入pair数组中，按照导弹高度快速排序，然后二分找到高于当前查找的导弹的最小高度，再对这个找到的位置及之后的所有导弹按照dp值排序，取最后一个+1就是当前导弹的dp最大值。 然后求第二问，用dp存每个系统的最小导弹高度，利用二分找到高于当前导弹高度的最小系统高度，求出当前导弹所在的系统（无法在前面系统则新开一个系统），然后对所有系统的最小高度值进行快速排序。

总觉得这个思路的时间复杂度就是O(nlogn)，但实际运行的时间还不如没优化前的O(n^2)，请教各位大佬，帮忙改改代码。

//导弹拦截

//导弹的最高高度非递增
//求最多能拦截多少导弹和最少要配备多少套导弹拦截系统 
//不能用单调栈
//找最长的非递增子序列 
//每套系统用能打到的最小高度标记 

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 1e5 + 10;

typedef pair<int,int> PII;

int h[N];//导弹的高度 
int n;//导弹个数
int dp[N];//dp[i]:以i号导弹结尾的最长非递增子序列 
int cnt = 0;//多少套 
int m = 0;//最多能拦截多少导弹 
int sum = 0;//已经拦截的导弹数

//快速排序1
void quick_sort1(vector<PII> &res,int l,int r){
	if(l >= r){
		return;
	}
	
	PII x = res[l];
	int i = l - 1,j = r + 1;
	while(i < j){
		do{
			i++;
		}while(res[i].first < x.first);
		do{
			j--;
		}while(res[j].first > x.first);
		if(i < j){
			swap(res[i],res[j]);
		}
	}
	
	quick_sort1(res,l,j);
	quick_sort1(res,j + 1,r);
} 

//快速排序
void quick_sort2(vector<PII> &res,int l,int r){
	if(l >= r){
		return;
	}
	
	PII x = res[l];
	int i = l - 1,j = r + 1;
	while(i < j){
		do{
			i++;
		}while(res[i].second < x.second);
		do{
			j--;
		}while(res[j].second > x.second);
		if(i < j){
			swap(res[i],res[j]);
		}
	}
	
	quick_sort2(res,l,j);
	quick_sort2(res,j + 1,r);
}

//快速排序
void quick_sort3(int l,int r){
	if(l >= r){
		return;
	}
	
	int x = dp[l];
	int i = l - 1,j = r + 1;
	while(i < j){
		do{
			i++;
		}while(dp[i] < x);
		do{
			j--;
		}while(dp[j] > x);
		if(i < j){
			swap(dp[i],dp[j]);
		}
	}
	
	quick_sort3(l,j);
	quick_sort3(j + 1,r);
} 

//二分查找
int bsearch1(vector<PII> res,int x){
	int l = 0,r = res.size() - 1;
	int mid = (l + r) >> 1;
	int a,b;
	
	while(l < r){
		mid = (l + r) >> 1;
		a = res[mid].first;
		b = res[mid].second;
		
		if(a >= x){
			r = mid;
		}else{
			l = mid + 1;
		}
	}
	
	if(res[l].first < x){
		//没有符合条件的 
		return -1;
	}
	
	//快速排序
	quick_sort2(res,l,res.size() - 1);
	
	return res[res.size() - 1].second;
} 

//二分查找
int bsearch2(int x){
	int l = 1,r = cnt;
	int mid = (l + r) >> 1;
	
	while(l < r){
		mid = (l + r) >> 1;
		if(dp[mid] >= x){
			r = mid;
		}else{
			l = mid + 1;
		}
	}
	
	if(dp[l] < x){
		//没有符合条件的 
		return -1;
	}
	
	return l; 
} 

//第一问的动态规划 
int f1(){
	int ans = 1;
	vector<PII> res;//按顺序存所有dp结果
	dp[1] = 1;
	res.push_back({h[1],dp[1]});
  
	//枚举所有导弹
	for(int i = 2;i <= n;i++){
		//找前面所有的可拦截导弹个数最多的
		dp[i] = 1;
		int a;
		int b;
		//二分查找第一个大于等于自己高度的
		int t = bsearch1(res,h[i]);
		if(t != -1){
			//有符合条件的
			dp[i] = t + 1; 
		}
		res.push_back({h[i],dp[i]});
		if(ans < dp[i]){
			ans = dp[i];
		}
		//重新排序
		quick_sort1(res,0,res.size() - 1);
	} 
	
	return ans;
}
//第二问
void f2(){
	//枚举所有导弹 
	for(int i = 1;i <= n;i++){
		//找前面的系统中最低导弹高度最小的大于等于当前导弹高度的
		//从小到大枚举所有导弹系统 
		bool flag = false;//是否找到了可以打到的系统 
		
		//二分查找上一个大于自己的最小值 
		int t = bsearch2(h[i]);
		if(t != -1){
			//有符合条件的 
			flag = true;
			dp[t] = h[i]; 
			//printf("dp[%d]=%d\n",t,dp[t]);
		}
		
		if(!flag){
			//没有系统可以打到
			//新开一个系统
			cnt++;
			dp[cnt] = h[i]; 
		}

		quick_sort3(1,cnt);
	}
} 

int main(){
	//输入
	/*do{
		n++;
		scanf("%d",&h[n]);
	}while(getchar() != '\n');*/
	while(scanf("%d",&h[n + 1]) != EOF){
		n++;
	}

	//判断一套系统最多能拦截多少导弹 
	m = f1();
	
	//判断需要多少套
	memset(dp,0,sizeof(dp));
	f2();
	
	//输出
	printf("%d\n%d",m,cnt); 
	
	return 0;
}