Cod sursa(job #729644)

Utilizator BoSs_De_BosSSeFu SeFiLoR BoSs_De_BosS Data 29 martie 2012 19:38:20
Problema Walls Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#include<stdio.h>
#include<map>

#define maxn 100005
#define mp make_pair

using namespace std;

FILE*f=fopen("walls.in","r");
FILE*g=fopen("walls.out","w");

int n,i,x,y,p,poz,q;
int w[maxn],h[maxn],Arb[4*maxn];
long long X[maxn];
map< pair<int,int> , int >M;
map< pair<int,int> , int >::iterator itt;

inline int cb ( int val ){
	int p,m,u;
	p = 1; u = n;
	
	while ( p <= u ){
		m = (p + u) >> 1;
		if ( val >= X[m] )
			p = m + 1;
		else
			u = m - 1;
	}
	
	return u;
}

void update ( int nod , int st , int dr ){
	
	if ( st == dr ){
		Arb[nod] = st;
		return ;
	}
	
	int mij = (st + dr) >> 1;
	int nodst = nod << 1;
	int noddr = nodst + 1;
	
	if ( poz <= mij ){
		update(nodst,st,mij);
	}
	else{
		update(noddr,mij+1,dr);
	}
	
	Arb[nod] = h[Arb[nodst]] > h[Arb[noddr]] ? Arb[nodst] : Arb[noddr];
}

int query ( int nod , int st , int dr ){
	
	if ( st > p )	return -1;
	if ( dr <= p ){
		if ( h[Arb[nod]] < y )
			return -1;
		if ( st == dr ){
			if ( h[Arb[nod]] >= y )
				return Arb[nod];
			return -1;
		}
	}
	
	int mij = (st + dr) >> 1;
	int nodst = nod << 1;
	int noddr = nodst + 1;
	
	int v = query(noddr,mij+1,dr);
	if ( v == -1 ){
		v = query(nodst,st,mij);
	}
	
	return v;
}

int main () {
	
	fscanf(f,"%d",&n);
	X[0] = -1;
	for ( i = 1 ; i <= n ; ++i ){
		fscanf(f,"%d %d",&w[i],&h[i]);
		X[i] = X[i-1] + w[i] + 1;
		poz = i;
		update(1,1,n);
	}
	
	fscanf(f,"%d",&q);
	for ( i = 1 ; i <= q ; ++i ){
		fscanf(f,"%d %d",&x,&y);
		
		p = cb(x);
		int res = query(1,1,n);
		
		if ( res == -1 ){
			fprintf(g,"MISS\n");
			continue ;
		}
		
		fprintf(g,"HIT ");
		
		++M[mp(res,y)];
		itt = M.find(mp(res,y));
		
		fprintf(g,"%d ",X[res] - (itt)->second +1);
		
		int dob = 0;
		if ( (itt)->second == w[res] ){
			dob = 1;
			(itt)->second = 0; h[res] = y - 1;
			poz = res; update(1,1,n);
		}
		
		fprintf(g,"%d ",res);
		if ( dob )
			fprintf(g,"YES\n");
		else
			fprintf(g,"NO\n");
	}
	
	return 0;
}