水题
以后交题目一定要检查调试有没有删掉
因为这个WA了一次……
简单的单调栈
#include<cstdio>
#include<stack>
using namespace std;
stack<int> S;
int n,w,ans,f[500005]={0};
int main(){
freopen("1683.in","r",stdin);
freopen("1683.out","w",stdout);
scanf("%d %d",&n,&w);
for(int i=1;i<=n;i++){
int tpa,tpb;
scanf("%d %d",&tpa,&tpb);
int last=-1;
while(!S.empty() && S.top()>tpb){int res=S.top();S.pop();if(res!=last){ans++;last=res;}}
S.push(tpb);
}
while(!S.empty()){
if(f[S.top()]==0 && S.top()){
f[S.top()]++;
ans++;
}
S.pop();
}
printf("%d\n",ans);
return 0;
}
评论 (0)
