Cod sursa(job #547381)

Utilizator AndreyPAndrei Poenaru AndreyP Data 6 martie 2011 12:06:50
Problema Walls Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.85 kb
#include <cstdio>
#include <set>
#include <algorithm>
using namespace std;
#define ll long long
#define fs first
#define sc second
#define mp make_pair
#define pll pair< ll,ll >
#define N 100010
#define pil pair< int,ll >

int n,m;
int a[3*N];
ll v[2*N];
int cw[2*N];
int h[N];
set< pil > s[N];
int pr,ul,ret,q;
pll wall[N];
template< class T >
inline T maxim(T x,T y) {
	return ((x>y) ? x : y);
}

inline void citire() {
	scanf("%d",&n);
	ll x;
	int aux=0;
	v[0] = -1;
	for(int i=1; i<=n; ++i) {
		scanf("%lld%d",&x,&h[i]);
		v[aux+1] = v[aux]+2;
		v[aux+2] = v[aux+1]+x-1;
		cw[aux+1] = cw[aux+2] = i;
		wall[i] = mp(v[aux+1],v[aux+2]);
		aux += 2;
	}
}

void init(int p,int u,int i) {
	if(p>u)
		return;
	if(p==u) {
		a[i] = h[p];
		return;
	}
	
	int m = (p+u)>>1;
	init(p,m,(i<<1));
	init(m+1,u,((i<<1)+1));
	
	a[i] = maxim(a[(i<<1)],a[((i<<1)+1)]);
}

void query(int p,int u,int i) {
	if(p>u)
		return;
	
	if(p==u) {
		ret = p;
		return;
	}
	
	if(a[i]<q)
		return;
	
	int m = (p+u)>>1;
	if(u<=ul) {
		if(a[((i<<1)+1)]>=q)
			query(m+1,u,((i<<1)+1));
		else
			query(p,m,(i<<1));
		return;
	}
	
	if(m+1<=ul && a[((i<<1)+1)]>=q)
		query(m+1,u,((i<<1)+1));
	if(ret==0 && a[(i<<1)]>=q)
		query(p,m,(i<<1));
}

inline int caut(ll x) {
	int p=1,u=(n<<1),m;
	
	while(p<u) {
		m = (p+u)>>1;
		if(x<=v[m])
			u = m;
		else
			p = m+1;
	}
	
	if(v[p]>x)
		--p;
	return cw[p];
}

void update(int p,int u,int i) {
	if(p>u)
		return;
	
	if(p==u) {
		a[i] = h[p];
		return;
	}
	
	int m = (p+u)>>1;
	
	if(pr<=m)
		update(p,m,(i<<1));
	else
		update(m+1,u,((i<<1)+1));
	
	a[i] = maxim(a[(i<<1)],a[((i<<1)+1)]);
}

inline void rezolva() {
	init(1,n,1);
	
	int m;
	scanf("%d",&m);
	ll x,y;
	set< pil >::iterator it;
	pil aux;
	for(int i=1; i<=m; ++i) {
		scanf("%lld%lld",&x,&y);
		if(y>a[1] || x<=1) {
			fputs("MISS\n",stdout);
			continue;
		}
		
		ul = caut(x);
		q = (int)y;
		ret = 0;
		query(1,n,1);
		
		if(ret==0) {
			fputs("MISS\n",stdout);
			continue;
		}
		
		it = s[ret].upper_bound(mp(y,wall[ret].fs-1));
		
		if(it==s[ret].end() || ((it->fs)!=y) || ((it->sc)>wall[ret].sc)) {
			aux.fs = y;
			aux.sc = wall[ret].sc-1;
			if(aux.sc>=wall[ret].fs) {
				printf("HIT %lld %d NO\n",wall[ret].sc,ret);
				s[ret].insert(aux);
			} else {
				printf("HIT %lld %d YES\n",wall[ret].sc,ret);
				pr = ret;
				h[ret] = y-1;
				update(1,n,1);
			}
			continue;
		}
		
		aux = *it;
		s[ret].erase(it);
		if(aux.sc==wall[ret].fs) {
			printf("HIT %lld %d YES\n",wall[ret].fs,ret);
			pr = ret;
			h[ret] = y-1;
			update(1,n,1);
		} else {
			printf("HIT %lld %d NO\n",aux.sc,ret);
			--aux.sc;
			s[ret].insert(aux);
		}
	}
}

int main() {
	freopen("walls.in","r",stdin);
	freopen("walls.out","w",stdout);
	
	citire();
	rezolva();
	
	return 0;
}