昨晚 ARC B 求调
  • 板块题目总版
  • 楼主Pig_py
  • 当前回复1
  • 已保存回复1
  • 发布时间2022/10/3 10:45
  • 上次更新2023/10/27 09:05:33
查看原帖
昨晚 ARC B 求调
448873
Pig_py楼主2022/10/3 10:45

TLE&WA,求指出哪里 WA 了。

#include<bits/stdc++.h>
using namespace std;
int n;
struct code{
	int a,b;
}e[300005];
int dp[300005];
bool cmp(const code u,const code v){
	return u.a<v.a;
}
struct sss{
	int id,num;
}f[300005];
signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&e[i].a);
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&e[i].b );
	}
	sort(e+1,e+n+1,cmp); 
	int ans=n;
	dp[1]=1;
	for(int i=1;i<=n;i++){
		if(i!=1){
			int l=1,r=i-1;
			int x,y;
			while(l<r){
				x=l,y=r;
				int mid=(l+r)/2;
				if(f[mid].num>=e[i].b){
					r=mid-1;
				}
				else if(mid+1<i&&f[mid+1].num<e[i].b )l=mid+1;
				else{
					break;
				}
				if(x==l&&y==r)break;
				//printf("%d %d %d\n",i,l,r);
			}			
			for(int j=1;j<=l;j++){
				dp[i]=max(dp[i],dp[f[j].id]+1);
			} 			
		}
		f[i].id=i;
		f[i].num=e[i].b;
		int cnt=i;
		while(cnt-1>=1&&f[cnt].num<f[cnt-1].num){
			swap(f[cnt].num,f[cnt-1].num);
			swap(f[cnt].id,f[cnt-1].id );
			cnt--;
		}
	}
	ans+=dp[n];
	printf("%d",ans);
}
2022/10/3 10:45
加载中...