首页 > 代码库 > CF 821C 模拟
CF 821C 模拟
x入栈的同时 也加入集合b,
当a.top()!=num 直接reorder复杂度为n^2logn 改为清空栈,当栈为空时 表示栈已经有序,删除元素直接从集合中删除.
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e6+20; int n,p[N]; char s[20]; stack<int> a; set<int> b; int main() { while(cin>>n) { int num=1,ans=0; int x; int top=0; n=2*n; for(int i=1;i<=n;i++) { scanf("%s",s); if(s[0]==‘a‘) { scanf("%d",&x); a.push(x),b.insert(x); } else { if(!a.empty()) { if(a.top()!=num)//reorder ?úb?D??3ynum { ans++;//cout<<num<<endl; while(!a.empty()) a.pop(); } else a.pop(); } //è????a???ò±íê? ?3Dò′óμ?D?1ì?¨?éò??ú,?ˉo?b?Dé?3y b.erase(num); num++; } } cout<<ans<<endl; } return 0; }
CF 821C 模拟
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。