简单的单调栈
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n,Stack[250005],Top,ans;
int main(){
freopen("1113.in","r",stdin);
freopen("1113.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x,y;
scanf("%d %d",&x,&y);
while(Top && Stack[Top]>=y){if(Stack[Top]!=y)ans++;Top--;}
Stack[++Top]=y;
}
printf("%d\n",ans+Top);
return 0;
}
评论 (0)
