tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

2011 Apples

みんなこの問題を動的にStarry Sky木を組んでやるとか言ってますが、そんなに動的っぽくは無いと思います。とはいってもこんな特殊なSegmentTreeはじめて書いた。配列からついに逸脱した。あと、mapを使って逃げることに成功しました。
map::iterator m=M.upper_bound(P);
というものをついに覚えました。iteratorは++や--ならできるらしい。
定数倍怖かったけど余裕で通っていた。

#include<stdio.h>
#include<algorithm>
#include<map>
using namespace std;
struct wolf{
	int left;
	int right;
	int val;
	int par;
	wolf(int t){
		left=right=-1;
		val=0;
		par=t;
	}
	wolf(){}
};
wolf segtree[5000000];
int del[100000];
int at;
void add(unsigned int a,unsigned int b,int c,int d,int e,int f){
	if(d<a||b<c)return;
	if(c<=a&&b<=d){
		segtree[e].val+=f;
	}else{
		if(segtree[e].left==-1){
			segtree[e].left=at;
			segtree[at++]=wolf(e);
 		}
		if(segtree[e].right==-1){
			segtree[e].right=at;
			segtree[at++]=wolf(e);
		}
		add(a,(a+b)/2,c,d,segtree[e].left,f);
		add((a+b)/2+1,b,c,d,segtree[e].right,f);
	}
	if(e){
		int s=segtree[e].par;
		if(~segtree[s].left&&~segtree[s].right){
			if(segtree[segtree[s].left].val>0||segtree[segtree[s].right].val>0||(segtree[segtree[s].left].val<0&&segtree[segtree[s].right].val<0)){
				int q=max(segtree[segtree[s].left].val,segtree[segtree[s].right].val);
				segtree[s].val+=q;
				segtree[segtree[s].left].val-=q;
				segtree[segtree[s].right].val-=q;
			}
		}
		else if(~segtree[s].left){
			segtree[s].val+=segtree[segtree[s].left].val;
			segtree[segtree[s].left]=0;
		}
		else if(~segtree[s].right){
			segtree[s].val+=segtree[segtree[s].right].val;
			segtree[segtree[s].right]=0;
		}
	}
}
int query(int a){
	if(segtree[0].val<a)return -1;
	int now=0;
	unsigned  left=0;
	unsigned right=2147483647;
	int v=segtree[0].val;
	while(left<right){
		if(~segtree[now].right&&v+segtree[segtree[now].right].val>=a){
			left=(left+right)/2+1;
			v+=segtree[segtree[now].right].val;
			now=segtree[now].right;
		}else{
			right=(left+right)/2;
			v+=segtree[segtree[now].left].val;
			now=segtree[now].left;
		}
	}
	return (int)left;
}
char in[2];
map<int,int>M;
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	segtree[at++]=wolf(-1);
	M[2147483647]=1;
	for(int i=0;i<a;i++){
		scanf("%s",in);
		int c;
		if(in[0]=='A'){
			scanf("%d",&c);
			if(M.count(c))M[c]=M[c]+1;
			else M[c]=1;
			add(0,2147483647,c,c+b,0,1);
		//	printf("%d\n",S.size());
		}else if(in[0]=='R'){
			scanf("%d",&c);
			int P=query(c);
			if(P==-1){
				printf("NO\n");
				fflush(stdout);
			}else{
				//P-=b;
				map<int,int>::iterator m=M.upper_bound(P);
				m--;
		//		printf("%d\n",P);
				int L=0;
				for(int j=0;j<c;j++){
					del[j]=(*m).first;
					if(!L)L=(*m).second;
					add(0,2147483647,del[j],del[j]+b,0,-1);
					L--;
					if(!L)m--;
				}
				for(int j=0;j<c;j++){
					if(j)printf(" ");
					printf("%d",del[c-1-j]);
				}
				for(int j=0;j<c;j++){
					M[del[j]]=M[del[j]]-1;
					if(M[del[j]]==0)M.erase(del[j]);
				}
				printf("\n");
				fflush(stdout);
		//	printf("%d\n",M.size());
			}
		}else return 0;
	}
}

ところで皆さんBeltといていてぱないと思います。1日に2回も幾何するほど気力がなかった。