Pagini recente » Cod sursa (job #858573) | Cod sursa (job #2882938) | Cod sursa (job #1568168) | Cod sursa (job #102782) | Cod sursa (job #544718)
Cod sursa(job #544718)
#include <cstdio>
#include <map>
using namespace std;
#define nmax 100010
struct punct
{
int x, y, w;
} v[nmax];
int n, poz, val, arb[4*nmax], rm, m, p[nmax], nod;
map <int, int> g[nmax];
void update(int nod, int l, int r)
{
if (l==r)
{
arb[nod]=poz;
p[poz]=nod;
if (rm<nod) rm=nod;
} else
{
int m=(l+r)/2;
if (poz<=m) update(2*nod, l, m); else
update(2*nod+1, m+1, r);
if (v[arb[2*nod+1]].y>=v[arb[2*nod]].y)
arb[nod]=arb[2*nod+1]; else
arb[nod]=arb[2*nod];
}
}
int search(int a, int b)
{
int m, r;
while (a<=b)
{
m=(a+b)/2;
if (v[m].x<val)
{
r=m;
a=m+1;
} else b=m-1;
}
return r;
}
int up(int nod)
{
if (v[arb[nod]].y>=val || nod==1) return nod;
return up(nod/2);
}
int query(int nod)
{
if (2*nod>rm) return arb[nod];
if (arb[2*nod+1]==arb[nod])
return query(2*nod+1); else
return query(2*nod);
}
int main()
{
freopen("walls.in","r",stdin);
freopen("walls.out","w",stdout);
int i, w, h, x, y, j;
scanf("%d",&n);
v[0].x=-1;
for (i=1; i<=n; i++)
{
scanf("%d %d", &w, &h);
v[i].y=h;
v[i].x=v[i-1].x+1+w;
v[i].w=w;
poz=i;
val=h;
update(1, 1, n);
}
scanf("%d",&m);
while (m--)
{
scanf("%d %d",&x, &y);
val=x;
x=search(1, n);
val=y;
nod=up(p[x]);
if (v[arb[nod]].y<y) printf("MISS\n"); else
{
printf("HIT ");
poz=query(nod);
printf("%d ",v[poz].x-g[poz][y]);
printf("%d ",poz);
g[poz][y]++;
if (g[poz][y]==v[poz].w)
{
printf("YES\n");
v[poz].y=y-1;
val=v[poz].y;
update(1, 1, n);
} else printf("NO\n");
}
}
}