[CF 705C]Thor

danihao123 posted @ 2016年8月08日 12:58 in 题解 with tags codeforces 队列 优化题 , 628 阅读
转载请注明出处:http://danihao123.is-programmer.com/

这题我考试的时候想出各种蜜汁数据结构。

但是正解是:暴力!

好了好了,暴力也是要优化的。首先给消息编号,然后用一个bitset记下来哪个删了哪个没删,这个都能想到。

不过接下来有个挺头疼的问题:操作3阅读的信息可能在操作2中会被再次阅读,如此一来效率就很低了……咋整?

注意大消息队列里的消息编号肯定是升序的,每个程序的消息队列的编号也是升序的,所以说大队列中同一程序的消息的编号和该程序自身队列中的消息编号的顺序是一致的。如此一来,在操作3中可以顺便把程序队列中的消息也删掉,效率大为提升。

代码:

#include <cstdio>
#include <queue>
#include <utility>
#include <cctype>
#include <bitset>
using namespace std;
const int maxn=300001;
typedef pair<int,int> pii;
bitset<maxn> vis;
queue<int> S[maxn];
queue<pii> Q;
// I/O优化
inline int readint(){
    char c=getchar();
    register int x=0;
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int bf[10];
inline void writeint(int x){
    register int p=0;
    if(x==0){
        bf[p++]=0;
    }else{
        while(x){
            bf[p++]=x%10;
            x/=10;
        }
    }
    for(register int i=p-1;i>=0;i--)
        putchar('0'+bf[i]);
}
int main(){
	register int ans=0,cnt=0;
	register int temp,temp_2,q,u,v;
	int n;
	n=readint();
	q=readint();
	while(q--){
		u=readint();
		v=readint();
		if(u==1){
			cnt++;
			S[v].push(cnt);
			Q.push(make_pair(v,cnt));
			ans++;
		}else{
			if(u==2){
				while(!S[v].empty()){
					temp=S[v].front();
					S[v].pop();
					if(!vis[temp]){
						vis[temp]=true;
						ans--;
					}
				}
			}else{
				while(!Q.empty() && (temp=Q.front().second)<=v){
					temp=Q.front().second;
					temp_2=Q.front().first;
					Q.pop();
					if(!vis[temp]){
						vis[temp]=true;
						S[temp_2].pop();
						ans--;
					}
				}
			}
		}
		writeint(ans);
		putchar('\n');
	}
	return 0;
}
www.model-paper.in 说:
Jul 03, 2023 11:18:58 AM

Better service in different forms and we do not sell or giveaway your personal information other than public info giving out by you. We are very conscious about mail spam and we try to protect every email as much as possible. In certain cases www.model-paper.in your mail may be exposed to public. Model-paper works on giving out better service in different forms and we do not sell or giveaway your personal information.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter