Nu aveti permisiuni pentru a descarca fisierul grader_test34.ok
Cod sursa(job #549098)
Utilizator | Data | 8 martie 2011 10:00:48 | |
---|---|---|---|
Problema | Walls | Scor | 50 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.45 kb |
#include <stdio.h>
#include <algorithm>
#include <map>
using namespace std;
#define MAXN 100010
long long st;
long long XWall[MAXN];
int HWall[2*MAXN], Lat[MAXN];
int i,ind,N,M,Y,y, x, X;
int find1(int nod, int st, int dr, int X, int H)
{
if (st>dr || XWall[st]>X || HWall[nod]<H) return -1;
if (st==dr) return st;
int mij = (st+dr)>>1;
int aux = find1((nod<<1)+1, mij+1, dr, X,H);
if (aux == -1)
aux = find1((nod<<1), st, mij, X,H);
return aux;
}
void update(int nod, int st, int dr, int poz, int X)
{
if (st>dr) return;
if (st==dr){
HWall[nod] = X;
return;
}
int mij=(st+dr)>>1;
if (mij >= poz)
update((nod<<1), st, mij, poz, X);
else
update((nod<<1)+1, mij+1, dr, poz, X);
HWall[nod] = max(HWall[(nod<<1)], HWall[(nod<<1)+1]);
}
int main()
{
freopen("walls.in","r",stdin);
freopen("walls.out","w",stdout);
scanf("%d",&N);
st = 1LL;
for (i=1; i<=N; ++i){
scanf("%d %d",&x,&y);
XWall[i] = st;
st = st+x+1;
Lat[i] = x;
update(1, 1, N, i, y);
}
map<pair<int, int>, int> Hit;
scanf("%d",&M);
for (i=1; i<=M; ++i){
scanf("%d %d",&X,&Y);
ind = find1(1, 1, N, X, Y);
if (ind == -1){
printf("MISS\n");
continue;
}
int &nr = Hit[make_pair(ind, Y)];
++nr;
printf("HIT %lld ", XWall[ind]+Lat[ind]-nr);
printf("%d ", ind);
if (nr == Lat[ind]){
printf("YES\n");
update(1, 1, N, ind, Y-1);
}
else
printf("NO\n");
}
return 0;
}