Cod sursa(job #546109)

Utilizator Bogdan_tmmTirca Bogdan Bogdan_tmm Data 4 martie 2011 13:54:21
Problema Walls Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.5 kb
#include<algorithm>
#include<vector>
#include<set>

using namespace std;
#define N_MAX 100005

struct nivel_s
{
	int inaltime;
	mutable int grosime;
	
	nivel_s()
	{
	}
	
	bool operator < (const nivel_s &other) const
	{
		return this->inaltime<other.inaltime;
	}
	
};

struct zid_s
{
	int latime,inaltime,poz;
	set <nivel_s> nivele;
	
	zid_s()
	{
		latime=inaltime=poz=0;
	}
};

zid_s aux;
zid_s ziduri[N_MAX];

set <nivel_s> ::iterator it,it2,it3;
nivel_s aux2;

int aint[N_MAX*5];
int n,m,i,j,x,y;

void update(int nod,int st,int dr,int a,int b,int poz)
{
	if(a<=st&&dr<=b)
	{
		aint[nod]=poz;
		return ;
	}
	
	int md=(st+dr)>>1;
	int ST=(nod<<1);
	int DR=(nod<<1)+1;
	
	if(a<=md)
		update(ST,st,md,a,b,poz);
	if(md<b)
		update(DR,md+1,dr,a,b,poz);
	
 	aint[nod]=aint[ST];
	
	if(ziduri[ aint[nod] ].inaltime<ziduri[ aint[DR] ].inaltime)
		aint[nod]=aint[DR];
}

int query(int nod,int st,int dr,int a,int b)
{
	if(a<=st&&dr<=b)
	{
		return aint[nod];
	}
	
	int md=(st+dr)>>1;
	int ST=(nod<<1);
	int DR=(nod<<1)+1;
	int pozMax=0,pz;
	
	if(a<=md)
	{
		pz=query(ST,st,md,a,b);
		
		if(ziduri[pz].inaltime>ziduri[pozMax].inaltime)
			pozMax=pz;
	}
	if(md<b)
	{
		pz=query(DR,md+1,dr,a,b);
		
		if(ziduri[pz].inaltime>ziduri[pozMax].inaltime)
			pozMax=pz;
	}
	
	return pozMax;
}

void hit(int hit,int x,int y,int op)
{
	if(hit==0)
	{
		printf("MISS\n");
		return;
	}
	printf("HIT %d %d ",x,y);
	
	if(op==0)
		printf("NO\n");
	else
		printf("YES\n");
}

int main()
{
	freopen("walls.in","r",stdin);
	freopen("walls.out","w",stdout);
	
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d%d",&x,&y);
		
		aux.latime=x;
		aux.inaltime=y;
		aux.poz=ziduri[i-1].poz+ziduri[i-1].latime+1;
		
		ziduri[i]=aux;
		
		update(1,1,n,i,i,i);
	}
	
	int lg,LOG,zidDr,zidLovit,pozMax;
	for(LOG=1;LOG<n;(LOG<<=1));
	
	scanf("%d",&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		
		lg=LOG;
		
		for(j=0;lg;(lg>>=1))
			if(j+lg<=n&&ziduri[j+lg].poz<=x)
				j+=lg;
		
		zidDr=j;
		
		if(zidDr==0)
		{
			hit(0,0,0,0);
			continue;
		}
		
		lg=LOG;
		zidLovit=0;
		for(j=0;lg;(lg>>=1))
		{
			if(j+lg>zidDr)
				continue;
			
			pozMax=query(1,1,n,j+lg,zidDr);
			
			if(ziduri[pozMax].inaltime>=y)
			{
				zidLovit=pozMax;
				j+=lg;
			}
		}
		
		if(zidLovit==0)
		{
			hit(0,0,0,0);
			continue;
		}
		
		aux2.inaltime=y;
		aux2.grosime=ziduri[zidLovit].latime;
		
		it=ziduri[zidLovit].nivele.find(aux2);
		
		int distrus=0;
		
		if(it==ziduri[zidLovit].nivele.end())
		{
			aux2.grosime--;
			ziduri[zidLovit].nivele.insert(aux2);
			
			if(aux2.grosime==0)
			{
				it2=ziduri[zidLovit].nivele.find(aux2);
				it3=it2;
				it3++;
				while(it3!=ziduri[zidLovit].nivele.end())
				{
					ziduri[zidLovit].nivele.erase(it3);
					it3=it2;
					it3++;
				}
				ziduri[zidLovit].nivele.erase(it2);
				
				ziduri[zidLovit].inaltime=y-1;
				update(1,1,n,zidLovit,zidLovit,zidLovit);
				distrus=1;
			}
		}
		else
		{
			it->grosime--;
			aux2.grosime=it->grosime;
			
			if(it->grosime==0)
			{
				it3=it;
				it3++;
				while(it3!=ziduri[zidLovit].nivele.end())
				{
					ziduri[zidLovit].nivele.erase(it3);
					it3=it;
					it3++;
				}
				ziduri[zidLovit].nivele.erase(it);
				
				ziduri[zidLovit].inaltime=y-1;
				update(1,1,n,zidLovit,zidLovit,zidLovit);
				distrus=1;
			}
		}
		
		hit(1,aux2.grosime+ziduri[zidLovit].poz,zidLovit,distrus);
	}
	
	return 0;
}