Pagini recente » Cod sursa (job #3137996) | Cod sursa (job #634220) | Cod sursa (job #2317619) | Cod sursa (job #2758958) | Cod sursa (job #545044)
Cod sursa(job #545044)
#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], m, p[nmax], nod, rn;
char d[4*nmax], f[4*nmax];
map <int, int> g[nmax];
void update(int nod, int l, int r)
{
if (l==1) f[nod]=1;
if (l==r)
{
arb[nod]=poz;
d[nod]=1;
p[poz]=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=0;
while (a<=b)
{
m=(a+b)/2;
if (v[m].x<val)
{
r=m;
a=m+1;
} else b=m-1;
}
return r;
}
void up(int nod)
{
if (v[arb[rn]].y>=val || nod==1); else
{
if (nod%2)
if (v[arb[nod-1]].y>=v[arb[rn]].y) rn=nod-1;
up(nod/2);
}
}
int query(int nod)
{
if (d[nod]) return arb[nod];
if (arb[2*nod+1]==arb[nod] || v[arb[2*nod+1]].y>=val)
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;
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;
rn=p[x];
if (x) up(p[x]);
nod=rn;
if (v[arb[nod]].y<y || !x) 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");
}
}
}