竞赛讨论区 > 周赛13提高组T2单调队列为啥错求指点
头像
LB_tq
发布于 2019-12-07 22:00
+ 关注

周赛13提高组T2单调队列为啥错求指点

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=1e5+10;
int n,n1,n2,a[maxn][2],b[maxn][2];
int p[maxn],t,ans;
int fr(){
	char ch=getchar();
	while(ch>'9'||ch<'0')
		ch=getchar();
	int sum=ch-'0';
	while((ch=getchar())>='0'&&ch<='9')
		sum=(sum<<3)+(sum<<1)+ch-'0';
	return sum;
}
int main() {
	n=fr();
	int x,y;
	for(int i=1;i<=n;i++){
		x=fr(); y=fr();
		if(x<y){
			a[++n1][0]=x;
			a[n1][1]=y;
		}
		if(x>y){
			b[++n2][0]=x;
			b[n2][1]=y;
		}
	}
	p[++t]=a[1][1];
	for(int i=2;i<=n1;i++){
		if(a[i][0]<p[t])
			p[++t]=a[i][1];
		else if(a[i][1]>p[t]&&(t==1||p[t-1]>a[i][0])){
			t--;
			p[++t]=a[i][1];
		}
	}
	ans=t;
	t=0;
	p[++t]=b[1][1];
	for(int i=2;i<=n2;i++){
		if(b[i][0]>p[t])
			p[++t]=b[i][1];
		else if(b[i][1]<p[t]&&(t==1||p[t-1]<b[i][0])){
			t--;
			p[++t]=b[i][1];
		}
	}
	ans=max(ans,t);
	printf("%d",ans);
	return 0;
}

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐